HashMap的用法信赖我不消说了然，常用于无序键值对的存放，因为其有杰出的查找和插入机能，是多量应用的数据布局。HashMap相干的办法有get，put，常见的参数包含loadFactor，Capacity等，在后面都邑提到。经常被提到的另两个类似的类是HashTable和java.util.concurrent.ConcurrentHashMap ，这三个类首要差别是多线程时辰的机能以及是否线程安然，一言以蔽之：机能HashMap>ConcurrentHashMap>HashTable，然则HashMap长短线程安然的，其余则安然。

　　比来口试老被问到hashMap的实现，于是花了点时候对其完全的看了一遍。话不久不多说，进入正题。

根蒂根基的道理

　　java.util.HashMap中有一个Entry[] table ，数据都存放在这个里面。

　　

　　起首entry是用于实现链表的一个节点，有key，value用于存储自身节点数据，还有next用于下个节点的引用。

　　再看HashMap中的get办法：

　　

　　我们可以获得这几个结论：

　　

　　get就是查找对应entry的过程，entry链被放在table数组这n个桶里

　　1.对nullkey做零丁处理惩罚，其实就是放在table[0]中。

　　2.按照key的hash值，决意entry在哪个桶。

　　3.对桶内的entry链表进行遍历，当查找到时返回value。

　　4.找不到，返回null

 

　　这里要插一个不相干的，要遍历hashmap必须经由过程hashmap.entrySet（）.iterator（）来遍历，前者本身没有实现iterable必然要重视。entrySet就是保存entry的Set凑集类

　　再次重申，hashmap没有实现collection 接口和iterable接口

 

loadFactor 和 initCapacity

 

　　我们看HashMap的默认机关函数：

　　

　　

　　//最大容量  

　　static final int MAXIMUM_CAPACITY = 1 << 30; 

　　//默认加载因子，加载因子是一个比例，当HashMap的数据大小>=容量加载因子时，HashMap会将容量扩容  

　　static final float DEFAULT_LOAD_FACTOR = 0.75f;  

　　//阈值，当实际数据大小跨越threshold时，HashMap会将容量扩容，threshold＝容量加载因子

　　int threshold; 

　　//加载因子 

　　final float loadFactor;

 

　　可以清楚地看到，默认我们是机关了一个初始容量为16，加载因子为0.75f的一个map。第一次扩容产生在什么时辰呢？160.75=12

 

有趣的细节

　　

　　容量老是2的倍数，为什么呢？为了寻址的快速。

　　寻址是经由过程 index & （table.length-1）实现的，其实就是一个取模，若是table.length 是2的倍数的话，table.length-1 老是 111111... 的布局，与运算可以便利的获得mod值。

 

　　为什么不消类的hashcode，而是要再做一次hash？避免最坏景象。

　　int hash = hash（key.hashcode（））; ----拜见上文的get办法

　　我们来看hash函数干了什么。

　　

　　

　　从注释上可以看出：这个函数以位移和异或的体式格式包管了hashcode不会有最坏景象呈现（即大多半kv都分到了同一个桶）。在默认的加载因子下最坏不跨越8的冲突。其实就是让分布加倍的均化。

　　引用了StackOverflow上方的老外申明：

　　

　
关于扩容　

　　

　　之前提到了当容量达到阈值后，HashMap会进行扩容。扩容时干了什么呢？

　　

　　可以看到，做的工作包含：

　　1.从头申请空间存放table

　　2.transfer（把老数据移到新的table中），并将table指向到新的table（之后老table主动垃圾收集掉）

　　3.调剂新的threshold值，以便下一次的resize可以或许在put办法中被激活

 

　　若是研究put办法可以看到：

　　在put中有这么一个断定       

　　

1 if （size++ >= threshold） 

2  resize（2  table.length）;

View Code

   　size的申明是The number of key-value mappings contained in this map. 而threshold已经申明过了。也就是说put时会对元素数量进行搜检，并视景象进行扩容。