java源码研究-HashMap
添加时间:2013-5-28 点击量:
HashMap的用法信赖我不消说了然，常用于无序键值对的存放，因为其有杰出的查找和插入机能，是多量应用的数据布局。HashMap相干的办法有get，put，常见的参数包含loadFactor，Capacity等，在后面都邑提到。经常被提到的另两个类似的类是HashTable和java.util.concurrent.ConcurrentHashMap ，这三个类首要差别是多线程时辰的机能以及是否线程安然，一言以蔽之：机能HashMap>ConcurrentHashMap>HashTable，然则HashMap长短线程安然的，其余则安然。
比来口试老被问到hashMap的实现，于是花了点时候对其完全的看了一遍。话不久不多说，进入正题。
根蒂根基的道理
java.util.HashMap中有一个Entry[] table ，数据都存放在这个里面。
Entry是HashMap中的一个静态内部类。用于实现一个链表布局，节点默示map中的一个值，从定义可以看出：
起首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时会对元素数量进行搜检，并视景象进行扩容。
HashMap的用法信赖我不消说了然，常用于无序键值对的存放，因为其有杰出的查找和插入机能，是多量应用的数据布局。HashMap相干的办法有get，put，常见的参数包含loadFactor，Capacity等，在后面都邑提到。经常被提到的另两个类似的类是HashTable和java.util.concurrent.ConcurrentHashMap ，这三个类首要差别是多线程时辰的机能以及是否线程安然，一言以蔽之：机能HashMap>ConcurrentHashMap>HashTable，然则HashMap长短线程安然的，其余则安然。
比来口试老被问到hashMap的实现，于是花了点时候对其完全的看了一遍。话不久不多说，进入正题。
根蒂根基的道理
java.util.HashMap中有一个Entry[] table ，数据都存放在这个里面。
Entry是HashMap中的一个静态内部类。用于实现一个链表布局，节点默示map中的一个值，从定义可以看出：
起首entry是用于实现链表的一个节点，有key，value用于存储自身节点数据，还有next用于下个节点的引用。
我们看HashMap的默认机关函数：
再看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中有这么一个断定
View Code
1 if （size++ >= threshold）
2 resize（2 table.length）;
View Code
size的申明是The number of key-value mappings contained in this map. 而threshold已经申明过了。也就是说put时会对元素数量进行搜检，并视景象进行扩容。
