非線性容器

2024-02-16 13:47 更新

非線性容器實現能快速查找的數據結構，其底層通過hash或者紅黑樹實現，包括HashMap、HashSet、TreeMap、TreeSet、LightWeightMap、LightWeightSet、PlainArray七種。非線性容器中的key及value的類型均滿足ECMA標準。

HashMap

HashMap可用來存儲具有關聯關系的key-value鍵值對集合，存儲元素中key是唯一的，每個key會對應一個value值。

HashMap依據泛型定義，集合中通過key的hash值確定其存儲位置，從而快速找到鍵值對。HashMap的初始容量大小為16，并支持動態(tài)擴容，每次擴容大小為原始容量的2倍。HashMap底層基于HashTable實現，沖突策略采用鏈地址法。

HashMap和TreeMap相比，HashMap依據鍵的hashCode存取數據，訪問速度較快。而TreeMap是有序存取，效率較低。

HashSet基于HashMap實現。HashMap的輸入參數由key、value兩個值組成。在HashSet中，只對value對象進行處理。

需要快速存取、刪除以及插入鍵值對數據時，推薦使用HashMap。

HashMap進行增、刪、改、查操作的常用API如下：

操作

描述

增加元素

通過set(key: K, value: V)函數每次在HashMap增加一個鍵值對。

訪問元素

通過get(key: K)獲取key對應的value值。

通過keys()返回一個迭代器對象，包含map中的所有key值。

通過values()返回一個迭代器對象，包含map中的所有value值。

通過entries()返回一個迭代器對象，包含map中的所有鍵值對。

forEach(callbackFn: (value?: V, key?: K, map?: HashMap<K, V>) => void, thisArg?: Object)訪問整個map的元素。

通過[Symbol.iterator]():IterableIterator<[K,V]>迭代器進行數據訪問。

修改元素

通過replace(key: K, newValue: V)對指定key對應的value值進行修改操作。

通過forEach(callbackFn: (value?: V, key?: K, map?: HashMap<K, V>) => void, thisArg?: Object)對map中元素進行修改操作。

刪除元素

通過remove(key: K)對map中匹配到的鍵值對進行刪除操作。

通過clear()清空整個map集合。

HashSet

HashSet可用來存儲一系列值的集合，存儲元素中value是唯一的。

HashSet依據泛型定義，集合中通過value的hash值確定其存儲位置，從而快速找到該值。HashSet初始容量大小為16，支持動態(tài)擴容，每次擴容大小為原始容量的2倍。value的類型滿足ECMA標準中要求的類型。HashSet底層數據結構基于HashTable實現，沖突策略采用鏈地址法。

HashSet基于HashMap實現。在HashSet中，只對value對象進行處理。

HashSet和TreeSet相比，HashSet中的數據無序存放，即存放元素的順序和取出的順序不一致，而TreeSet是有序存放。它們集合中的元素都不允許重復，但HashSet允許放入null值，TreeSet不建議插入空值，可能會影響排序結果。

可以利用HashSet不重復的特性，當需要不重復的集合或需要去重某個集合的時候使用。

HashSet進行增、刪、改、查操作的常用API如下：

操作

描述

增加元素

通過add(value: T)函數每次在HashSet增加一個值。

訪問元素

通過values()返回一個迭代器對象，包含set中的所有value值。

通過entries()返回一個迭代器對象，包含類似鍵值對的數組，鍵值都是value。

通過forEach(callbackFn: (value?: T, key?: T, set?: HashSet<T>) => void, thisArg?: Object)訪問整個set的元素。

通過[Symbol.iterator]():IterableIterator<T>迭代器進行數據訪問。

修改元素

通過forEach(callbackFn: (value?: T, key?: T, set?: HashSet<T>) => void, thisArg?: Object)對set中value進行修改操作。

刪除元素

通過remove(value: T)對set中匹配到的值進行刪除操作。

通過clear()清空整個set集合。

TreeMap

TreeMap可用來存儲具有關聯關系的key-value鍵值對集合，存儲元素中key是唯一的，每個key會對應一個value值。

TreeMap依據泛型定義，集合中的key值是有序的，TreeMap的底層是一棵二叉樹，可以通過樹的二叉查找快速的找到鍵值對。key的類型滿足ECMA標準中要求的類型。TreeMap中的鍵值是有序存儲的。TreeMap底層基于紅黑樹實現，可以進行快速的插入和刪除。

TreeMap和HashMap相比，HashMap依據鍵的hashCode存取數據，訪問速度較快。而TreeMap是有序存取，效率較低。

一般需要存儲有序鍵值對的場景，可以使用TreeMap。

TreeMap進行增、刪、改、查操作的常用API如下：

操作

描述

增加元素

通過set(key: K,value: V)函數每次在TreeMap增加一個鍵值對。

訪問元素

通過get(key: K)獲取key對應的value值。

通過getFirstKey()獲取map中排在首位的key值。

通過getLastKey()獲取map中排在未位的key值。

通過keys()返回一個迭代器對象，包含map中的所有key值。

通過values()返回一個迭代器對象，包含map中的所有value值。

通過entries()返回一個迭代器對象，包含map中的所有鍵值對。

通過forEach(callbackFn: (value?: V, key?: K, map?: TreeMap<K, V>) => void, thisArg?: Object)訪問整個map的元素。

通過[Symbol.iterator]():IterableIterator<[K,V]>迭代器進行數據訪問。

修改元素

通過replace(key: K,newValue: V)對指定key對應的value值進行修改操作。

通過forEach(callbackFn: (value?: V, key?: K, map?: TreeMap<K, V>) => void, thisArg?: Object)對map中元素進行修改操作。

刪除元素

通過remove(key: K)對map中匹配到的鍵值對進行刪除操作。

通過clear()清空整個map集合。

TreeSet

TreeSet可用來存儲一系列值的集合，存儲元素中value是唯一的。

TreeSet依據泛型定義，集合中的value值是有序的，TreeSet的底層是一棵二叉樹，可以通過樹的二叉查找快速的找到該value值，value的類型滿足ECMA標準中要求的類型。TreeSet中的值是有序存儲的。TreeSet底層基于紅黑樹實現，可以進行快速的插入和刪除。

TreeSet基于TreeMap實現，在TreeSet中，只對value對象進行處理。TreeSet可用于存儲一系列值的集合，元素中value唯一且有序。

TreeSet和HashSet相比，HashSet中的數據無序存放，而TreeSet是有序存放。它們集合中的元素都不允許重復，但HashSet允許放入null值，TreeSet不建議插入空值，可能會影響排序結果。

一般需要存儲有序集合的場景，可以使用TreeSet。

TreeSet進行增、刪、改、查操作的常用API如下：

操作

描述

增加元素

通過add(value: T)函數每次在TreeSet增加一個值。

訪問元素

通過values()返回一個迭代器對象，包含set中的所有value值。

通過entries()返回一個迭代器對象，包含類似鍵值對的數組，鍵值都是value。

通過getFirstValue()獲取set中排在首位的value值。

通過getLastValue()獲取set中排在未位的value值。

通過forEach(callbackFn: (value?: T, key?: T, set?: TreeSet<T>) => void, thisArg?: Object)訪問整個set的元素。

通過[Symbol.iterator]():IterableIterator<T>迭代器進行數據訪問。

修改元素

通過forEach(callbackFn: (value?: T, key?: T, set?: TreeSet<T>) => void, thisArg?: Object)對set中value進行修改操作。

刪除元素

通過remove(value: T)對set中匹配到的值進行刪除操作。

通過clear()清空整個set集合。

LightWeightMap

LightWeightMap可用來存儲具有關聯關系的key-value鍵值對集合，存儲元素中key是唯一的，每個key會對應一個value值。LightWeightMap依據泛型定義，采用更加輕量級的結構，底層標識唯一key通過hash實現，其沖突策略為線性探測法。集合中的key值的查找依賴于hash值以及二分查找算法，通過一個數組存儲hash值，然后映射到其他數組中的key值以及value值，key的類型滿足ECMA標準中要求的類型。

初始默認容量大小為8，每次擴容大小為原始容量的2倍。

LightWeightMap和HashMap都是用來存儲鍵值對的集合，LightWeightMap占用內存更小。

當需要存取key-value鍵值對時，推薦使用占用內存更小的LightWeightMap。

LightWeightMap進行增、刪、改、查操作的常用API如下：

操作

描述

增加元素

通過set(key: K,value: V)函數每次在LightWeightMap增加一個鍵值對。

訪問元素

通過get(key: K)獲取key對應的value值。

通過getIndexOfKey(key: K)獲取map中指定key的index。

通過getIndexOfValue(value: V)獲取map中指定value出現的第一個的index。

通過keys()返回一個迭代器對象，包含map中的所有key值。

通過values()返回一個迭代器對象，包含map中的所有value值。

通過entries()返回一個迭代器對象，包含map中的所有鍵值對。

通過getKeyAt(index: number)獲取指定index對應的key值。

通過getValueAt(index: number)獲取指定index對應的value值。

通過forEach(callbackFn: (value?: V, key?: K, map?: LightWeightMap<K, V>) => void, thisArg?: Object)訪問整個map的元素。

通過[Symbol.iterator]():IterableIterator<[K,V]>迭代器進行數據訪問。

修改元素

通過setValueAt(index: number, newValue: V)對指定index對應的value值進行修改操作。

通過forEach(callbackFn: (value?: V, key?: K, map?: LightWeightMap<K, V>) => void, thisArg?: Object)對map中元素進行修改操作。

刪除元素

通過remove(key: K)對map中匹配到的鍵值對進行刪除操作。

通過removeAt(index: number)對map中指定index的位置進行刪除操作。

通過clear()清空整個map集合。

LightWeightSet

LightWeightSet可用來存儲一系列值的集合，存儲元素中value是唯一的。

LightWeightSet依據泛型定義，采用更加輕量級的結構，初始默認容量大小為8，每次擴容大小為原始容量的2倍。集合中的value值的查找依賴于hash以及二分查找算法，通過一個數組存儲hash值，然后映射到其他數組中的value值，value的類型滿足ECMA標準中要求的類型。

LightWeightSet底層標識唯一value基于hash實現，其沖突策略為線性探測法，查找策略基于二分查找法。

LightWeightSet和HashSet都是用來存儲鍵值的集合，LightWeightSet的占用內存更小。

當需要存取某個集合或是對某個集合去重時，推薦使用占用內存更小的LightWeightSet。

LightWeightSet進行增、刪、改、查操作的常用API如下：

操作

描述

增加元素

通過add(obj: T)函數每次在LightWeightSet增加一個值。

訪問元素

通過getIndexOf(key: T)獲取對應的index值。

通過values()返回一個迭代器對象，包含map中的所有value值。

通過entries()返回一個迭代器對象，包含map中的所有鍵值對。

通過getValueAt(index: number)獲取指定index對應的value值。

通過forEach(callbackFn: (value?: T, key?: T, set?: LightWeightSet<T>) => void, thisArg?: Object)訪問整個set的元素。

通過[Symbol.iterator]():IterableIterator<T>迭代器進行數據訪問。

修改元素

通過forEach(callbackFn: (value?: T, key?: T, set?: LightWeightSet<T>) => void, thisArg?: Object)對set中元素進行修改操作。

刪除元素

通過remove(key: K)對set中匹配到的鍵值對進行刪除操作。

通過removeAt(index: number)對set中指定index的位置進行刪除操作。

通過clear()清空整個set集合。

PlainArray

PlainArray可用來存儲具有關聯關系的鍵值對集合，存儲元素中key是唯一的，并且對于PlainArray來說，其key的類型為number類型。每個key會對應一個value值，類型依據泛型的定義，PlainArray采用更加輕量級的結構，集合中的key值的查找依賴于二分查找算法，然后映射到其他數組中的value值。

初始默認容量大小為16，每次擴容大小為原始容量的2倍。

PlainArray和LightWeightMap都是用來存儲鍵值對，且均采用輕量級結構，但PlainArray的key值類型只能為number類型。

當需要存儲key值為number類型的鍵值對時，可以使用PlainArray。

PlainArray進行增、刪、改、查操作的常用API如下：

操作

描述

增加元素

通過add(key: number,value: T)函數每次在PlainArray增加一個鍵值對。

訪問元素

通過get(key: number)獲取key對應的value值。

通過getIndexOfKey(key: number)獲取PlainArray中指定key的index。

通過getIndexOfValue(value: T)獲取PlainArray中指定value的index。

通過getKeyAt(index: number)獲取指定index對應的key值。

通過getValueAt(index: number)獲取指定index對應的value值。

通過forEach(callbackFn: (value: T, index?: number, PlainArray?: PlainArray<T>) => void, thisArg?: Object)訪問整個plainarray的元素。

通過[Symbol.iterator]():IterableIterator<[number, T]>迭代器進行數據訪問。

修改元素

通過setValueAt(index:number, value: T)對指定index對應的value值進行修改操作。

通過forEach(callbackFn: (value: T, index?: number, PlainArray?: PlainArray<T>) => void, thisArg?: Object)對plainarray中元素進行修改操作。

刪除元素

通過remove(key: number)對plainarray中匹配到的鍵值對進行刪除操作。

通過removeAt(index: number)對plainarray中指定index的位置進行刪除操作。

通過removeRangeFrom(index: number, size: number)對plainarray中指定范圍內的元素進行刪除操作。

通過clear()清空整個PlainArray集合。

非線性容器的使用

此處列舉常用的非線性容器HashMap、TreeMap、LightWeightMap、PlainArray的使用示例，包括導入模塊、增加元素、訪問元素及修改等操作，示例代碼如下所示：

  1. // HashMap
  2. import HashMap from '@ohos.util.HashMap'; // 導入HashMap模塊
  3. 

  4. let hashMap = new HashMap();
  5. hashMap.set('a', 123);
  6. hashMap.set(4, 123); // 增加元素
  7. console.info(`result: ${hashMap.hasKey(4)}`); // 判斷是否含有某元素
  8. console.info(`result: ${hashMap.get('a')}`); // 訪問元素
  9. 

  10. // TreeMap
  11. import TreeMap from '@ohos.util.TreeMap'; // 導入TreeMap模塊
  12. 

  13. let treeMap = new TreeMap();
  14. treeMap.set('a', 123);
  15. treeMap.set('6', 356); // 增加元素
  16. console.info(`result: ${treeMap.get('a')}`); // 訪問元素
  17. console.info(`result: ${treeMap.getFirstKey()}`); // 訪問首元素
  18. console.info(`result: ${treeMap.getLastKey()}`); // 訪問尾元素
  19. 

  20. // LightWeightMap
  21. import LightWeightMap from '@ohos.util.LightWeightMap'; // 導入LightWeightMap模塊
  22. 

  23. let lightWeightMap = new LightWeightMap();
  24. lightWeightMap.set('x', 123);
  25. lightWeightMap.set('8', 356); // 增加元素
  26. console.info(`result: ${lightWeightMap.get('a')}`); // 訪問元素
  27. console.info(`result: ${lightWeightMap.get('x')}`); // 訪問元素
  28. console.info(`result: ${lightWeightMap.getIndexOfKey('8')}`); // 訪問元素
  29. 

  30. // PlainArray
  31. import PlainArray from '@ohos.util.PlainArray' // 導入PlainArray模塊
  32. 

  33. let plainArray = new PlainArray();
  34. plainArray.add(1, 'sdd');
  35. plainArray.add(2, 'sff'); // 增加元素
  36. console.info(`result: ${plainArray.get(1)}`); // 訪問元素
  37. console.info(`result: ${plainArray.getKeyAt(1)}`); // 訪問元素
以上內容是否對您有幫助：
在線筆記
App下載
App下載

掃描二維碼

下載編程獅App

公眾號
微信公眾號

編程獅公眾號