非線性容器

2024-02-16 13:47 更新

非線性容器實(shí)現(xiàn)能快速查找的數(shù)據(jù)結(jié)構(gòu)，其底層通過(guò)hash或者紅黑樹(shù)實(shí)現(xiàn)，包括HashMap、HashSet、TreeMap、TreeSet、LightWeightMap、LightWeightSet、PlainArray七種。非線性容器中的key及value的類型均滿足ECMA標(biāo)準(zhǔn)。

HashMap

HashMap可用來(lái)存儲(chǔ)具有關(guān)聯(lián)關(guān)系的key-value鍵值對(duì)集合，存儲(chǔ)元素中key是唯一的，每個(gè)key會(huì)對(duì)應(yīng)一個(gè)value值。

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

HashMap和TreeMap相比，HashMap依據(jù)鍵的hashCode存取數(shù)據(jù)，訪問(wèn)速度較快。而TreeMap是有序存取，效率較低。

HashSet基于HashMap實(shí)現(xiàn)。HashMap的輸入?yún)?shù)由key、value兩個(gè)值組成。在HashSet中，只對(duì)value對(duì)象進(jìn)行處理。

需要快速存取、刪除以及插入鍵值對(duì)數(shù)據(jù)時(shí)，推薦使用HashMap。

HashMap進(jìn)行增、刪、改、查操作的常用API如下：

操作

描述

增加元素

通過(guò)set(key: K, value: V)函數(shù)每次在HashMap增加一個(gè)鍵值對(duì)。

訪問(wèn)元素

通過(guò)get(key: K)獲取key對(duì)應(yīng)的value值。

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

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

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

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

通過(guò)[Symbol.iterator]():IterableIterator<[K,V]>迭代器進(jìn)行數(shù)據(jù)訪問(wèn)。

修改元素

通過(guò)replace(key: K, newValue: V)對(duì)指定key對(duì)應(yīng)的value值進(jìn)行修改操作。

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

刪除元素

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

通過(guò)clear()清空整個(gè)map集合。

HashSet

HashSet可用來(lái)存儲(chǔ)一系列值的集合，存儲(chǔ)元素中value是唯一的。

HashSet依據(jù)泛型定義，集合中通過(guò)value的hash值確定其存儲(chǔ)位置，從而快速找到該值。HashSet初始容量大小為16，支持動(dòng)態(tài)擴(kuò)容，每次擴(kuò)容大小為原始容量的2倍。value的類型滿足ECMA標(biāo)準(zhǔn)中要求的類型。HashSet底層數(shù)據(jù)結(jié)構(gòu)基于HashTable實(shí)現(xiàn)，沖突策略采用鏈地址法。

HashSet基于HashMap實(shí)現(xiàn)。在HashSet中，只對(duì)value對(duì)象進(jìn)行處理。

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

可以利用HashSet不重復(fù)的特性，當(dāng)需要不重復(fù)的集合或需要去重某個(gè)集合的時(shí)候使用。

HashSet進(jìn)行增、刪、改、查操作的常用API如下：

操作

描述

增加元素

通過(guò)add(value: T)函數(shù)每次在HashSet增加一個(gè)值。

訪問(wèn)元素

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

通過(guò)entries()返回一個(gè)迭代器對(duì)象，包含類似鍵值對(duì)的數(shù)組，鍵值都是value。

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

通過(guò)[Symbol.iterator]():IterableIterator<T>迭代器進(jìn)行數(shù)據(jù)訪問(wèn)。

修改元素

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

刪除元素

通過(guò)remove(value: T)對(duì)set中匹配到的值進(jìn)行刪除操作。

通過(guò)clear()清空整個(gè)set集合。

TreeMap

TreeMap可用來(lái)存儲(chǔ)具有關(guān)聯(lián)關(guān)系的key-value鍵值對(duì)集合，存儲(chǔ)元素中key是唯一的，每個(gè)key會(huì)對(duì)應(yīng)一個(gè)value值。

TreeMap依據(jù)泛型定義，集合中的key值是有序的，TreeMap的底層是一棵二叉樹(shù)，可以通過(guò)樹(shù)的二叉查找快速的找到鍵值對(duì)。key的類型滿足ECMA標(biāo)準(zhǔn)中要求的類型。TreeMap中的鍵值是有序存儲(chǔ)的。TreeMap底層基于紅黑樹(shù)實(shí)現(xiàn)，可以進(jìn)行快速的插入和刪除。

TreeMap和HashMap相比，HashMap依據(jù)鍵的hashCode存取數(shù)據(jù)，訪問(wèn)速度較快。而TreeMap是有序存取，效率較低。

一般需要存儲(chǔ)有序鍵值對(duì)的場(chǎng)景，可以使用TreeMap。

TreeMap進(jìn)行增、刪、改、查操作的常用API如下：

操作

描述

增加元素

通過(guò)set(key: K,value: V)函數(shù)每次在TreeMap增加一個(gè)鍵值對(duì)。

訪問(wèn)元素

通過(guò)get(key: K)獲取key對(duì)應(yīng)的value值。

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

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

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

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

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

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

通過(guò)[Symbol.iterator]():IterableIterator<[K,V]>迭代器進(jìn)行數(shù)據(jù)訪問(wèn)。

修改元素

通過(guò)replace(key: K,newValue: V)對(duì)指定key對(duì)應(yīng)的value值進(jìn)行修改操作。

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

刪除元素

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

通過(guò)clear()清空整個(gè)map集合。

TreeSet

TreeSet可用來(lái)存儲(chǔ)一系列值的集合，存儲(chǔ)元素中value是唯一的。

TreeSet依據(jù)泛型定義，集合中的value值是有序的，TreeSet的底層是一棵二叉樹(shù)，可以通過(guò)樹(shù)的二叉查找快速的找到該value值，value的類型滿足ECMA標(biāo)準(zhǔn)中要求的類型。TreeSet中的值是有序存儲(chǔ)的。TreeSet底層基于紅黑樹(shù)實(shí)現(xiàn)，可以進(jìn)行快速的插入和刪除。

TreeSet基于TreeMap實(shí)現(xiàn)，在TreeSet中，只對(duì)value對(duì)象進(jìn)行處理。TreeSet可用于存儲(chǔ)一系列值的集合，元素中value唯一且有序。

TreeSet和HashSet相比，HashSet中的數(shù)據(jù)無(wú)序存放，而TreeSet是有序存放。它們集合中的元素都不允許重復(fù)，但HashSet允許放入null值，TreeSet不建議插入空值，可能會(huì)影響排序結(jié)果。

一般需要存儲(chǔ)有序集合的場(chǎng)景，可以使用TreeSet。

TreeSet進(jìn)行增、刪、改、查操作的常用API如下：

操作

描述

增加元素

通過(guò)add(value: T)函數(shù)每次在TreeSet增加一個(gè)值。

訪問(wèn)元素

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

通過(guò)entries()返回一個(gè)迭代器對(duì)象，包含類似鍵值對(duì)的數(shù)組，鍵值都是value。

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

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

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

通過(guò)[Symbol.iterator]():IterableIterator<T>迭代器進(jìn)行數(shù)據(jù)訪問(wèn)。

修改元素

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

刪除元素

通過(guò)remove(value: T)對(duì)set中匹配到的值進(jìn)行刪除操作。

通過(guò)clear()清空整個(gè)set集合。

LightWeightMap

LightWeightMap可用來(lái)存儲(chǔ)具有關(guān)聯(lián)關(guān)系的key-value鍵值對(duì)集合，存儲(chǔ)元素中key是唯一的，每個(gè)key會(huì)對(duì)應(yīng)一個(gè)value值。LightWeightMap依據(jù)泛型定義，采用更加輕量級(jí)的結(jié)構(gòu)，底層標(biāo)識(shí)唯一key通過(guò)hash實(shí)現(xiàn)，其沖突策略為線性探測(cè)法。集合中的key值的查找依賴于hash值以及二分查找算法，通過(guò)一個(gè)數(shù)組存儲(chǔ)hash值，然后映射到其他數(shù)組中的key值以及value值，key的類型滿足ECMA標(biāo)準(zhǔn)中要求的類型。

初始默認(rèn)容量大小為8，每次擴(kuò)容大小為原始容量的2倍。

LightWeightMap和HashMap都是用來(lái)存儲(chǔ)鍵值對(duì)的集合，LightWeightMap占用內(nèi)存更小。

當(dāng)需要存取key-value鍵值對(duì)時(shí)，推薦使用占用內(nèi)存更小的LightWeightMap。

LightWeightMap進(jìn)行增、刪、改、查操作的常用API如下：

操作

描述

增加元素

通過(guò)set(key: K,value: V)函數(shù)每次在LightWeightMap增加一個(gè)鍵值對(duì)。

訪問(wèn)元素

通過(guò)get(key: K)獲取key對(duì)應(yīng)的value值。

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

通過(guò)getIndexOfValue(value: V)獲取map中指定value出現(xiàn)的第一個(gè)的index。

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

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

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

通過(guò)getKeyAt(index: number)獲取指定index對(duì)應(yīng)的key值。

通過(guò)getValueAt(index: number)獲取指定index對(duì)應(yīng)的value值。

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

通過(guò)[Symbol.iterator]():IterableIterator<[K,V]>迭代器進(jìn)行數(shù)據(jù)訪問(wèn)。

修改元素

通過(guò)setValueAt(index: number, newValue: V)對(duì)指定index對(duì)應(yīng)的value值進(jìn)行修改操作。

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

刪除元素

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

通過(guò)removeAt(index: number)對(duì)map中指定index的位置進(jìn)行刪除操作。

通過(guò)clear()清空整個(gè)map集合。

LightWeightSet

LightWeightSet可用來(lái)存儲(chǔ)一系列值的集合，存儲(chǔ)元素中value是唯一的。

LightWeightSet依據(jù)泛型定義，采用更加輕量級(jí)的結(jié)構(gòu)，初始默認(rèn)容量大小為8，每次擴(kuò)容大小為原始容量的2倍。集合中的value值的查找依賴于hash以及二分查找算法，通過(guò)一個(gè)數(shù)組存儲(chǔ)hash值，然后映射到其他數(shù)組中的value值，value的類型滿足ECMA標(biāo)準(zhǔn)中要求的類型。

LightWeightSet底層標(biāo)識(shí)唯一value基于hash實(shí)現(xiàn)，其沖突策略為線性探測(cè)法，查找策略基于二分查找法。

LightWeightSet和HashSet都是用來(lái)存儲(chǔ)鍵值的集合，LightWeightSet的占用內(nèi)存更小。

當(dāng)需要存取某個(gè)集合或是對(duì)某個(gè)集合去重時(shí)，推薦使用占用內(nèi)存更小的LightWeightSet。

LightWeightSet進(jìn)行增、刪、改、查操作的常用API如下：

操作

描述

增加元素

通過(guò)add(obj: T)函數(shù)每次在LightWeightSet增加一個(gè)值。

訪問(wèn)元素

通過(guò)getIndexOf(key: T)獲取對(duì)應(yīng)的index值。

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

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

通過(guò)getValueAt(index: number)獲取指定index對(duì)應(yīng)的value值。

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

通過(guò)[Symbol.iterator]():IterableIterator<T>迭代器進(jìn)行數(shù)據(jù)訪問(wèn)。

修改元素

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

刪除元素

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

通過(guò)removeAt(index: number)對(duì)set中指定index的位置進(jìn)行刪除操作。

通過(guò)clear()清空整個(gè)set集合。

PlainArray

PlainArray可用來(lái)存儲(chǔ)具有關(guān)聯(lián)關(guān)系的鍵值對(duì)集合，存儲(chǔ)元素中key是唯一的，并且對(duì)于PlainArray來(lái)說(shuō)，其key的類型為number類型。每個(gè)key會(huì)對(duì)應(yīng)一個(gè)value值，類型依據(jù)泛型的定義，PlainArray采用更加輕量級(jí)的結(jié)構(gòu)，集合中的key值的查找依賴于二分查找算法，然后映射到其他數(shù)組中的value值。

初始默認(rèn)容量大小為16，每次擴(kuò)容大小為原始容量的2倍。

PlainArray和LightWeightMap都是用來(lái)存儲(chǔ)鍵值對(duì)，且均采用輕量級(jí)結(jié)構(gòu)，但PlainArray的key值類型只能為number類型。

當(dāng)需要存儲(chǔ)key值為number類型的鍵值對(duì)時(shí)，可以使用PlainArray。

PlainArray進(jìn)行增、刪、改、查操作的常用API如下：

操作

描述

增加元素

通過(guò)add(key: number,value: T)函數(shù)每次在PlainArray增加一個(gè)鍵值對(duì)。

訪問(wèn)元素

通過(guò)get(key: number)獲取key對(duì)應(yīng)的value值。

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

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

通過(guò)getKeyAt(index: number)獲取指定index對(duì)應(yīng)的key值。

通過(guò)getValueAt(index: number)獲取指定index對(duì)應(yīng)的value值。

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

通過(guò)[Symbol.iterator]():IterableIterator<[number, T]>迭代器進(jìn)行數(shù)據(jù)訪問(wèn)。

修改元素

通過(guò)setValueAt(index:number, value: T)對(duì)指定index對(duì)應(yīng)的value值進(jìn)行修改操作。

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

刪除元素

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

通過(guò)removeAt(index: number)對(duì)plainarray中指定index的位置進(jìn)行刪除操作。

通過(guò)removeRangeFrom(index: number, size: number)對(duì)plainarray中指定范圍內(nèi)的元素進(jìn)行刪除操作。

通過(guò)clear()清空整個(gè)PlainArray集合。

非線性容器的使用

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

  1. // HashMap
  2. import HashMap from '@ohos.util.HashMap'; // 導(dǎo)入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')}`); // 訪問(wèn)元素
  9. 

  10. // TreeMap
  11. import TreeMap from '@ohos.util.TreeMap'; // 導(dǎo)入TreeMap模塊
  12. 

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

  20. // LightWeightMap
  21. import LightWeightMap from '@ohos.util.LightWeightMap'; // 導(dǎo)入LightWeightMap模塊
  22. 

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

  30. // PlainArray
  31. import PlainArray from '@ohos.util.PlainArray' // 導(dǎo)入PlainArray模塊
  32. 

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

掃描二維碼

下載編程獅App

公眾號(hào)
微信公眾號(hào)

編程獅公眾號(hào)