hashmap演算法
① 面試中如何回答HashMap的工作原理
用過哪些Map類，都有什麼區別，HashMap是線程安全的嗎,並發下使用的Map是什麼，他們
內部原理分別是什麼，比如存儲方式，hashcode，擴容，默認容量等。
java8的ConcurrentHashMap為什麼放棄了分段鎖，有什麼問題嗎，如果你來設計，你如何
設計。
有沒有有順序的Map實現類，如果有，他們是怎麼保證有序的。
hashmap的實現原理，https://blog.csdn.net/mbshqqb/article/details/79799009
下面是自己的總結:
存儲結構:
裡面存儲的是一個entry數組，每個數組元素中的結構是一個entry鏈表
Entry是map中的一個靜態內部類，其中的變數有:key,value,hashcocd,下一個Entry
什麼是hash？
又稱散列，將任意長度的輸入通過散列演算法轉換成固定長度的輸出，該輸出就是散列值。這是一種壓縮映射，散列值的空間通常遠小於輸出的空間。不同的輸入有可能會散列出相同的輸出，因此不能從散列值來確定唯一的輸入值。這也是為什麼比較兩個對象不能僅僅使用hashcode方法比較的原因。
hash碰撞:
對不同的值進行hash運算生成了相同的散列值。這個是不可避免的，但是我們需要盡量的減少其帶來的損失。
(1)設計好的hash演算法讓其盡可能的分布均勻
hashmap中的hash演算法解析
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
讓key的hashcode本身與它右移16位異或，是為了讓它的高位與低位混合，增加低位的隨機性，同時也變相保持了高位的特徵
計算元素位置的演算法:
int index = hash & (arrays.length-1);
那麼這也就明白了為什麼HashMap的數組長度是2的整數冪。比如以初始長度為16為例，16-1 = 15，15的二進制數位00000000 00000000 00001111。可以看出一個基數二進制最後一位必然位1，當與一個hash值進行與運算時，最後一位可能是0也可能是1。但偶數與一個hash值進行與運算最後一位必然為0，造成有些位置永遠映射不上值。
對於null值的處理
hashmap是接受null值的，null值被放在數組的第一個元素當中，取出來的時候怎麼處理呢？
hashmap的工作原理？
它的裡面有一個Entry數組，在put時我們先根據key值計算出hashcode，進而計算出該元素在數組中的位置，將健值對封裝在Map.Entry對象中，然後存儲在數組中
若產生hash沖突怎麼辦？
每個數組元素的位置都是一個鏈表結構，若計算出來的hashcode相同則將元素追加到該鏈表當中，這是hashmap的處理方式
在取元素的時候，先計算key值對應的hashcode ，找到元素所在的位置，然後調用key的equals方法去遍歷鏈表，最後找到元素
還有哪些解決hash沖突的方法？
開放定址法
這種方法也稱再散列法，其基本思想是：當關鍵字key的哈希地址p=H（key）出現沖突時，以p為基礎，產生另一個哈希地址p1，如果p1仍然沖突，再以p為基礎，產生另一個哈希地址p2，…，直到找出一個不沖突的哈希地址pi ，將相應元素存入其中。
再哈希法
這種方法是同時構造多個不同的哈希函數：
Hi=RH1（key） i=1，2，…，k
當哈希地址Hi=RH1（key）發生沖突時，再計算Hi=RH2（key）……，直到沖突不再產生。這種方法不易產生聚集，但增加了計算時間。
鏈地址法
這種方法的基本思想是將所有哈希地址為i的元素構成一個稱為同義詞鏈的單鏈表，並將單鏈表的頭指針存在哈希表的第i個單元中，因而查找、插入和刪除主要在同義詞鏈中進行。鏈地址法適用於經常進行插入和刪除的情況。
建立公共溢出區
這種方法的基本思想是：將哈希表分為基本表和溢出表兩部分，凡是和基本表發生沖突的元素，一律填入溢出表。
默認的負載因子0.75
當map的大小超過當前容量的百分之75時會進行自動擴容，會將原來的對象重新放到新的數組中
rehash 的過程是什麼樣子的？
說白了就是先resize，生成一個新的Entry數組，再transfer將原數組中的值重新計算index放入新的數組中，然後改變閾值為新的長度x負載因子
如果key為null，這始終會被散列到table[0]的桶中，即使是rehash的過程也是一樣。非null的key也有可能會被散列到table[0]的位置，例如上圖中key=「f」，而且相同的key在在不同的時間可能會被散列到不同的位置，這與rehash有關。
這個過程中容易發生什麼問題呢？
容易產生條件競爭，如果在擴容的過程中put數據，會造成意想不到的結果。或者如果兩個線程都觸發了擴容，也會存在問題
這塊有沒有遇到過什麼比較好的例子？
jdk1.8以後改成了紅黑樹，為什麼？說一下紅黑樹的原理？
hashmap與hashtable的區別？
HashTable和HashMap的實現原理幾乎一樣，差別無非是
HashTable不允許key和value為null
HashTable是線程安全的
但是HashTable線程安全的策略實現代價卻太大了，簡單粗暴，get/put所有相關操作都是synchronized的，這相當於給整個哈希表加了一把大鎖。
多線程訪問時候，只要有一個線程訪問或操作該對象，那其他線程只能阻塞，相當於將所有的操作串列化，在競爭激烈的並發場景中性能就會非常差。
篇幅有限，未完待續
② JAVA中的HASHSET和HASHMap的底層實現是怎樣的大致講一下。
HASHMAP是根據HASH演算法儲存數據的集合類，每一個存入其中的對象都有一個特定的哈希值！當我們新建一個HashMap對象，如果不給定它的大小，其默認為16，就相當與下面新建了編號為0到15的數組(鏈表數組)。以默認HashMap為例，put一個對象時，首先得到他的哈希值，在與十五相除得到余數，找到與余數相同編號的數組插入其中！HASHSET就是沒有value值的HASHMAP，你可以新建一個HASHSET,插入0到15，絕對以0到15的順序列印。
③ HashMap底層實現原理剖析
Hashmap是一種非常常用的、應用廣泛的數據類型，最近研究到相關的內容，就正好復習一下。網上關於hashmap的文章很多，但到底是自己學習的總結，就發出來跟大家一起分享，一起討論。
1.HashMap的數據結構：在java 中 數據結構，最基本 也就兩種 一種數組 一種模擬指針。所有的數據結構都可以用這兩個基本結構來構造的，hashmap也不例外。Hashmap實際上是一個數組和鏈表的結合體。數組的默認長度為16，
2.hashMap源碼解析
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 初始化容量大小
static final int MAXIMUM_CAPACITY = 1 << 30; ///容器最大值
static final float DEFAULT_LOAD_FACTOR = 0.75f; //載入影子
static final Entry[] EMPTY_TABLE = {}; //null 的hashMap
transient Entry[] table = (Entry[]) EMPTY_TABLE;///動態擴大容器時使用的一個hashMap
transient int size;//當前數據量
int threshold;//擴大容器時的大小 為 capacity * load factor
final float loadFactor;//使用率閥值，默認為：DEFAULT_LOAD_FACTOR
存取元素 ：調用put方法
public V put(K key, V value) {
//判斷當前table 為Null 第一次Put
if (table == EMPTY_TABLE) {
inflateTable(threshold); //初始化容器的大小
}
if (key == null)
return putForNullKey(value); //判斷當前key 為null 將Null key添加到數組的第一個位置
int hash = hash(key); //將當前key進行hash 詳情見下方
int i = indexFor(hash, table.length); //調用完hash演算法後，詳情見下方
for (Entry e = table[i]; e != null; e = e.next) { //循環判斷當前數組下標為Entry的實體 將當前key相同的替換為最新的值
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i); //如果key都不同 則添加Entry.詳情見下方
return null;
}
hashMap的hash演算法剖析
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) { //判斷當前k是否為string 和
return sun.misc.Hashing.stringHash32((String) k); //使用stringHash32演算法得出key 的hash值
}
h ^= k.hashCode(); //調用key的hashCode 得出值 後使用"或"運算符
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
前面說過HashMap的數據結構是數組和鏈表的結合，所以我們當然希望這個HashMap裡面的 元素位置盡量的分布均勻些，盡量使得每個位置上的元素數量只有一個，那麼當我們用hash演算法求得這個位置的時候，馬上就可以知道對應位置的元素就是我們要的，而不用再去遍歷鏈表，這樣就大大優化了查詢的效率。
一個十進制數32768(二進制1000 0000 0000 0000)，經過上述公式運算之後的結果是35080(二進制1000 1001 0000 1000)。看出來了嗎？或許這樣還看不出什麼，再舉個數字61440(二進制1111 0000 0000 0000)，運算結果是65263(二進制1111 1110 1110 1111)，現在應該很明顯了，它的目的是讓「1」變的均勻一點，散列的本意就是要盡量均勻分布。使用上述演算法後 "1"就變得很均勻了。
我們用table[index]表示已經找到的元素需要存儲的位置。先判斷該位置上有沒有元素（這個元素是HashMap內部定義的一個類Entity， 基本結構它包含三個類，key，value和指向下一個Entity的next）,沒有的話就創建一個Entity對象，在 table[index]位置上插入，這樣插入結束；如果有的話，通過鏈表的遍歷方式去逐個遍歷，看看有沒有已經存在的key，有的話用新的value替 換老的value；如果沒有，則在table[index]插入該Entity，把原來在table[index]位置上的Entity賦值給新的 Entity的next，這樣插入結束
}
indexFor 返回當前數組下標 ，
static int indexFor(int h, int length) {
return h & (length-1);
}
那麼得到key 之後的hash如何得到數組下標呢 ？把h與HashMap的承載量（HashMap的默認承載量length是16，可以自動變長。在構造HashMap的時候也可以指定一個長 度。這個承載量就是上圖所描述的數組的長度。）進行邏輯與運算，即 h & (length-1)，這樣得到的結果就是一個比length小的正數，我們把這個值叫做index。其實這個index就是索引將要插入的值在數組中的 位置。第2步那個演算法的意義就是希望能夠得出均勻的index，這是HashTable的改進，HashTable中的演算法只是把key的 hashcode與length相除取余，即hash % length，這樣有可能會造成index分布不均勻。
首先來解釋一下為什麼數組大小為2的冪時hashmap訪問的性能最高？
看下圖，左邊兩組是數組長度為16（2的4次方），右邊兩組是數組長度為15。兩組的hashcode均為8和9，但是很明顯，當它們和1110「與」的時候，產生了相同的結果，也就是說它們會定位到數組中的同一個位置上去，這就產生了碰撞，8和9會被放到同一個鏈表上，那麼查詢的時候就需要遍歷這個鏈表，得到8或者9，這樣就降低了查詢的效率。同時，我們也可以發現，當數組長度為15的時候，hashcode的值會與14（1110）進行「與」，那麼最後一位永遠是0，而0001，0011，0101，1001，1011，0111，1101這幾個位置永遠都不能存放元素了，空間浪費相當大，更糟的是這種情況中，數組可以使用的位置比數組長度小了很多，這意味著進一步增加了碰撞的幾率，減慢了查詢的效率！
void addEntry(int hash, K key, V value, int bucketIndex) {
//// 若HashMap的實際大小 不小於 「閾值」，則調整HashMap的大小
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
//// 設置「bucketIndex」位置的元素為「新Entry」，// 設置「e」為「新Entry的下一個節點」
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
//將當前key 和value添加到Entry[]中
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry e = table[bucketIndex]; //將第一個就得table 復制個新的entry
table[bucketIndex] = new Entry<>(hash, key, value, e); //將當前新的Entry 復制個table[bucketIndex] 舊的table[bucketIndex] 和新的table[buckIndex]之間用next關聯。第一個鍵值對A進來，通過計算其key的hash得到的index=0，記做:table[0] = A。一會後又進來一個鍵值對B，通過計算其index也等於0，現在怎麼辦？HashMap會這樣做: B.next = A ,table[0] = B,如果又進來C,index也等於0,那麼 C.next = B ,table[0] = C；這樣我們發現index=0的地方其實存取了A,B,C三個鍵值對,他們通過next這個屬性鏈接在一起
size++; //容量加1
}
以上就是HashMap添加元素時的過程解析
那麼如何get元素呢？
public V get(Object key) {
if (key == null) return getForNullKey(); //當前key是否為null 如果為null值返回table[0]這個value
Entry entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final EntrygetEntry(Object key) {
if (size == 0) { return null; } //判斷容量是否大於0
int hash = (key == null) ? 0 : hash(key); //對當前key 進行hash hash後得到一個值
for (Entry e = table[indexFor(hash, table.length)]; //獲取當前Entry 循環遍歷
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
擴展問題:
1.當前我們的hashMap中越來越大的之後，"碰撞"就越來越明顯，那麼如何解決碰撞呢？擴容！
當hashmap中的元素個數超過數組大小capti*loadFactor時，就會進行數組擴容，loadFactor的默認值為0.75，也就是說，默認情況下，數組大小為16，那麼當hashmap中元素個數超過16*0.75=12的時候，就把數組的大小擴展為2*16=32，即擴大一倍，然後重新計算每個元素在數組中的位置，而這是一個非常消耗性能的操作，所以如果我們已經預知hashmap中元素的個數，那麼預設元素的個數能夠有效的提高hashmap的性能。比如說，我們有1000個元素new HashMap(1000), 但是理論上來講new HashMap(1024)更合適，不過上面annegu已經說過，即使是1000，hashmap也自動會將其設置為1024。 但是new HashMap(1024)還不是更合適的，因為0.75*1000 < 1000, 也就是說為了讓0.75 * size > 1000, 我們必須這樣new HashMap(2048)才最合適，既考慮了&的問題，也避免了resize的問題
HashMap的兩種遍歷方式
第一種
Map map = newHashMap();
Iterator iter = map.entrySet().iterator();
while(iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
Object key = entry.getKey();
Object val = entry.getValue();
}
效率高,以後一定要使用此種方式！
第二種
Map map = newHashMap();
Iterator iter = map.keySet().iterator();
while(iter.hasNext()) {
Object key = iter.next();
Object val = map.get(key);
}
效率低,以後盡量少使用！
歸納
簡單地說，HashMap 在底層將 key-value 當成一個整體進行處理，這個整體就是一個 Entry 對象。HashMap 底層採用一個 Entry[] 數組來保存所有的 key-value 對，當需要存儲一個 Entry 對象時，會根據hash演算法來決定其在數組中的存儲位置，在根據equals方法決定其在該數組位置上的鏈表中的存儲位置；當需要取出一個Entry時，
也會根據hash演算法找到其在數組中的存儲位置，再根據equals方法從該位置上的鏈表中取出該Entry。
④ 求高手給解答一下 HashMap 的存儲結構，說的越清楚越好，謝謝
HashMap存儲結構淺析
1.hashmap是按照存儲結構來講是數組(散列桶)與鏈表的組合體.
2. 如何計算hashmap中的散列桶的位置。
首先hashcode的值是用來輔助計算散列桶的位置的。如何散列有不同的演算法，比如%或 & (散列桶的length-1)
hashmap內部實現會把hashcode的值通過移位等運算再加工一下，保證加工之後的值二進制串中的01分布更加均勻. 數組的index或散列桶的位置等於h & (length-1); 由於length初始值是16, 將來也是基於2的倍數進行自動擴展. 所以length - 1的binary形式一定是一堆1，然後做與運算的結果就是取優化後哈希值的低位
index一定會<=length-1. 正好做為數組的下標. 注意，通常根據hashcode計算散列桶的演算法是%。
由於數組的長度默認是16,並且會以2的倍數resize，當數組變大之後，會將以前數組中的每個entry的key重新hash到新的數組里：index=h & (newlength-1)
3.與運算會將計算出的哈希值轉換成正的吧？上面有提到過溢出的問題，這樣可能會導致二進制符號位為1，得出的值是負數
->HashMap的代碼實現，裡面的MAX_CAPACITY是Integer Max Value的一半，也就是低位的部分不可能出現在符號位上
注:int是32位,通常最左邊的位是符號位. 如果數組的容量length最大的值才是Integer Max Value的一半,那麼與之後不會肯定影響到符號位的值.
4.字元串如何計算hashcode
for (int i = 0; i < len; i++) {
h = 31*h + val[off++];
}
如果h的值隨著字元串的增長而超過32整型的值.
不管它如何增大，它只取32位(即使超過32位)，所以說會出現負數(超過32位時,32位應該是1. 這樣截取之後,首位是1就會表示負數)。
hashcode的范圍就是一個int的范圍-2^32到2^31
5.
5. 散列的目的是索引化訪問
如果一個map使用array來實現，第一個array裡面存放key，第二個存放value，k-v的index一致。這樣的存儲結構，如果要去匹配某個key，需要遍歷key array的元素，才能找到。這樣查找的效率與array的長度成反比。散列表的出現就是在速度與存儲空間找到一個平衡並且每次查找的時間是恆定的, 散列表的目的就象通過index訪問array那樣，將一切索引化。比如通過hashcode去定位散列桶。散列桶中的元素有可能沖突。hashmap的解決是繼續通過equal去比較沖突的元素是否相等。
又例如hashmap的數組位置是0～7。又假如要把某個類的實例存放在以上8個位置中，如果不用hashcode而任意存放，那麼當查找時就需要到每個位置去找。
假如類中欄位ID,如果hash演算法是hashcode＝ID％8，以後在查找該類時就可以通過ID除8 求余數直接找到存放的位置。
但是如果兩個類的實例的hashcode被散列到同一個桶，例如9除以8和17除以8的余數都是1，這時9和17就存在沖突，這時就需要equals去進一步比較沖突的元素是否相等。
hashcode來定位實例的散列桶位置然後再通過 equals判斷該桶裡面的元素是否邏輯相等。
所以二者的用途一定要區分：equals是用來判斷是否邏輯相等。hashCode是與hashset,hashtable,hashmap之類的數據結構使用時，用來快速定位散列桶。
6.數據結構get/add與hashcode和equal
6.1 HashSet
對於Set介面的實現類HashSet，它是按照哈希演算法來存取集合中的對象，並且因為其繼承了Set介面，所以不允許加入相同的元素，這就要使用到equals()和hashCode()方法了。在往HashSet裡面添加對象的時候，在Add()的方法內部，它首先調用該對象的hashCode()方法，如果返回的哈希碼與集合已存在對象的哈希碼不一致（HashMap會緩存放入元素的hashcode值，方便比較，HashSet有可能一樣，如果存在一樣的hashcode，add失敗，直接返回），則add()方法認定該對象沒有與集合中的其它對象重復，那麼該對象將被添加進集合中。如果hashCode()方法返回的哈希碼與集合已存在對象的哈希碼一致，那麼將調用該對象的equals方法，進一步判斷其是否為同一對象（根據java規范，並不強制不相等的二個對象擁有不相等的hashcode，這樣就導致不相等的二個對象可能存在一樣的hashcode，所以，倒過來，先判斷hashcode相等並不能決定二個對象也一定相等，所以，還需要進一步判斷equal來決定，以便add即使hashcode相同，但是equal不同的元素到hashset里）.
6.2 HashMap 具體可以參考effective java 39~40
hashmap的contains方法與get類似，在使用contains之前，先檢查元素的類裡面是否實現了hashcode,equal方法。下面的示例中equal中使用id去判斷是否相等，hashcode裡面一樣，也只能使用id去生成。盡量使hashcode裡面的元素與equal裡面的元素一致。 具體原因可以參考effective java 39~41. 下面示例中直接使用id是因為從第三方調用返回的數據都有id值，並不是需要保存後才會生成id的場景。後一種就不能使用id去判斷了。
@Override
public int hashCode()
{
final int prime = 31;
int result = 1;
result = prime * result + ((m_sId == null) ? 0 : m_sId.hashCode());
return result;
}
@Override
public boolean equals(Object obj)
{
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
SNSProfile other = (SNSProfile) obj;
if (m_sId == null)
{
if (other.m_sId != null)
return false;
}
else if (!m_sId.equals(other.m_sId))
return false;
return true;
}
7.String 類的hashcode的生成函數中
for (int i = 0; i < len; i++) { h = 31*h + val[off++]; }
為什麼要用31×h，這個數字是怎麼算出來的或者說用31有什麼好處
->
這 種方法HashCode的計算方法可能最早出現在Brian W. Kernighan和Dennis M. Ritchie的《The C Programming Language》中，被認為是性價比最高的演算法（又被稱為times33演算法，因為C中乘數常量為33，JAVA中改為31），實際上，包括List在 內的大多數的對象都是用這種方法計算Hash值。
9.hashmap的容量是按照2的次方增長,所以length-1的二進制值都是1.
8.resize中的transfer方法
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j =0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e !=null) {
src[j] =null;
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
//將newTable[i]的引用（C裡面的指針）賦給了e.next。也就是使用了單鏈表的頭插入方式（還有種是在尾插入方式）
e.next = newTable[i];
newTable[i] = e;//將e插入後做為第一個節點。上一步e.next的指向是舊的第一個節點。
e = next;
} while (e !=null);
}
}
}
HashMap與LinkedHashMap的區別：LinkedHashMap中的key是按照插入的順序排序。不象HashMap的key是無序的。主要用在有序訪問map的場景
⑤ java 為什麼使用hashmap
首先當我們需要存儲數據的時候，動態數組雖然能夠自動擴容，但是必須在初始時刻指定初始容量。而對於那些在編譯時無法確定具體的數量即動態增長的數據，就需要用到Java集合類了。對於ArrayList 和 LinkedList，還有 Vector它們都有一些缺點，要麼插入刪除速度慢、要麼就是遍歷速度慢。那麼有沒有一種插入、刪除、遍歷都比較不錯的集合類呢？於是 HashMap 就出現了。HashMap 是一個散列表，它存儲的是一組鍵值對(key-value)的集合，並實現快速的查找。
（1）為了實現快速查找，HashMap 選擇了數組而不是鏈表。以利用數組的索引實現 O(1) 復雜度的查找效率。
（2）為了利用索引查找，HashMap 引入 Hash 演算法, 將 key 映射成數組下標: key -> Index。
（3）引入 Hash 演算法又導致了 Hash 沖突。為了解決 Hash 沖突，HashMap 採用鏈地址法，在沖突位置轉為使用鏈表存儲。
（4）鏈表存儲過多的節點又導致了在鏈表上節點的查找性能的惡化。為了優化查找性能，HashMap 在鏈表長度超過 8 之後轉而將鏈表轉變成紅黑樹，以將 O(n) 復雜度的查找效率提升至 O(log n)。
【綜上】
HashMap 存在的意義就是實現一種快速的查找並且插入、刪除性能都不錯的一種 K/V（key/value）數據結構。
附上一位博主的高見：網頁鏈接
⑥ Java hashMap合並演算法
用Kotlin語言寫了一下，Java只要把MutableMap改成Map就可以了
importkotlin.random.Random;
funmain(arg:Array<String>){
println("HelloWorld");
valmap:Map<String,String>=hashMapOf(
"1242"to"A31_001","2424"to"A31_001",
"3646"to"A31_002");
println("原map:$map");
valgroups:HashMap<String,MutableMap<String,String>>=hashMapOf();
for((k,v)inmap.entries){
if(!groups.containsKey(v))groups.put(v,hashMapOf());
valm=groups.getValue(v);
m.put(k,v);
}
println("重組新map:$groups");
//給換成新隨機id,沒必要但為滿足要求
valnewMap:HashMap<Int,MutableMap<String,String>>=hashMapOf();
varid:Int;
for(vingroups.values){
do{id=Random.nextInt();}
while(newMap.containsKey(id));
newMap.put(id,v);
}
println("新隨機生成ID:$newMap");
}
>Task:run
HelloWorld
原map:{1242=A31_001,3646=A31_002,2424=A31_001}
重組新map:{A31_002={3646=A31_002},A31_001={2424=A31_001,1242=A31_001}}
新隨機生成ID:{-91779881={2424=A31_001,1242=A31_001},2102779363={3646=A31_002}}
BUILDSUCCESSFULin0s
⑦ hashmap演算法復雜度為什麼為O(1)
因為hashMap內部維護了一個Entry數組，hashcode即數組下標，根據key.hashcode()即可在數組中get到Entry對象，即O(1)。當然，這是理想情況。
倘若數據量大，則可能發生hash碰撞，即一個hashcode可能對應多個key，這時候這個Entry數組中的元素就不是Entry了，而是一個Entry鏈表。調用map.get(key)的時候，遇到了鏈表，則會遍歷鏈表，調用equals方法比較key。當然，jdk8做了優化，鏈表長度超過8的時候，會轉變為紅黑樹結構。當然，除了數據量之外，發生hash碰撞的概率還跟負載因子loadFactor有關。
⑧ Android開發 HashMap如何排序
HashMap排序是數據結構與演算法中常見的一種排序演算法。本文即以Android平台為例來實現該演算法。
具體代碼如下： public static void main(String[] args) { Map<String, Integer> map = new HashMap<String, Integer>(); map.put("lisi", 5); map.put("lisi1", 1); map.put("lisi2", 3); map.put("lisi3", 9); List<Map.Entry<String, Integer>> infoIds = new ArrayList<Map.Entry<String, Integer>>( map.entrySet()); System.out.println("--------------排序前--------------"); for (int i = 0; i < infoIds.size(); i++) { String id = infoIds.get(i).toString(); System.out.println(id); } // 排序 Collections.sort(infoIds, new Comparator<Map.Entry<String, Integer>>() { public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) { return ( o1.getValue()-o2.getValue()); } }); System.out.println("--------------排序後--------------"); for (int i = 0; i < infoIds.size(); i++) { Entry<String,Integer> ent=infoIds.get(i); System.out.println(ent.getKey()+"="+ent.getValue()); }}
⑨ HashMap是什麼東西
HashMap，中文名哈希映射，HashMap是一個用於存儲Key-Value鍵值對的集合，每一個鍵值對也叫做Entry。這些個鍵值對（Entry）分散存儲在一個數組當中，這個數組就是HashMap的主幹。HashMap數組每一個元素的初始值都是Null。
HashMap是基於哈希表的 Map 介面的實現。此實現提供所有可選的映射操作，並允許使用 null 值和 null 鍵。（除了非同步和允許使用 null 之外，HashMap 類與 Hashtable 大致相同。）此類不保證映射的順序，特別是它不保證該順序恆久不變。
(9)hashmap演算法擴展閱讀：
因為HashMap的長度是有限的，當插入的Entry越來越多時，再完美的Hash函數也難免會出現index沖突的情況。
HashMap數組的每一個元素不止是一個Entry對象，也是一個鏈表的頭節點。每一個Entry對象通過Next指針指向它的下一個Entry節點。當新來的Entry映射到沖突的數組位置時，只需要插入到對應的鏈表即可。