hashmap底层实现
1底层自己实现
/**
* @Auther: liuhaidong
* Data: 2020/3/6 0006、23:53
* Description:
* @version: 1.0
*/
public class Test {
public class MyHashMap<K, V> {
private int CAPACITY = 16;
private int size = 0;
private MyEntry[] table;
public MyHashMap(int CAPACITY) {
this.CAPACITY = CAPACITY;
this.table = new MyEntry[CAPACITY];
}
public MyHashMap() {
this.table = new MyEntry[CAPACITY];
}
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = myHash(key);
int i = indexForTable(hash, CAPACITY);
for (MyEntry<K, V> e = table[i]; e != null; e = e.next) {
if (e.hash == hash && (e.key == key || e.key.equals(key))) {
V old = e.value;
e.value = value;
return old;
}
}
addEntry(hash, key, value, i);
return null;
}
public V get(K key) {
if (key == null)
return getForNullKey();
int hash = myHash(key);
int i = indexForTable(hash, CAPACITY);
for (MyEntry<K, V> e = table[i]; e != null; e = e.next) {
if (e.hash == hash && (e.key == key || e.key.equals(key)))
return e.value;
}
return null;
}
private V getForNullKey() {
for (MyEntry<K, V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
private void addEntry(int hash, K key, V value, int i) {
MyEntry<K, V> e = table[i];
table[i] = new MyEntry<K, V>(hash, key, value, e);
if (size == CAPACITY)
resize();
size++;
}
private void resize() {
CAPACITY= CAPACITY* 2;
MyEntry[] newtable = new MyEntry[CAPACITY];
for (MyEntry<K, V> entry : table) {
MyEntry<K, V> e = entry; // 取得旧Entry数组的每个元素
if (e != null) {
entry = null;// 释放旧Entry数组的对象引用（循环后，旧的Entry数组不再引用任何对象）
do {
MyEntry<K, V> next = e.next;
int i = indexForTable(e.hash, CAPACITY); // 重新计算每个元素在数组中的位置
e.next = newtable[i];
newtable[i] = e; // 将元素放在数组上
e = next; // 访问下一个Entry链上的元素
} while (e != null);
}
}
table = newtable;
}
private int indexForTable(int hash, int CAPACITY) {
return hash & (CAPACITY - 1);
}
private int myHash(K key) {
if (key == null)
return 0;
int h = key.hashCode();
h = h ^ (h >>> 16);
return h;
}
private V putForNullKey(V value) {
for (MyEntry<K, V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V old = e.value;
e.value = value;
return old;
}
}
addEntry(0, null, value, 0);
return null;
}
}
class MyEntry<K, V> {
public int hash;
public K key;
public V value;
public MyEntry<K, V> next;
public MyEntry(int hash, K key, V value, MyEntry<K, V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
}
HashMap里面key为null存放到哪？
/**
* Offloaded version of put for null keys
*/
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
} 当HashMap的put方法，第二个判断就是key为null的判断后进入putForNullKey(V value)这个方法
可以看到，前面那个for循环，是在talbe[0]链表中查找key为null的元素，如果找到，则将value重新赋值给这个元素的value，并返回原来的value。
如果上面for循环没找到则将这个元素添加到talbe[0]链表的表头。
结论：HashMap对象的key、value值均可为null。
HahTable对象的key、value值均不可为null。
且两者的的key值均不能重复，若添加key相同的键值对，后面的value会自动覆盖前面的value，但不会报错。
大家都知道Hashtable与HashMap的三大区别，其中有一条则是HashMap可以存储一个Key为null，多个value为null的元素，但是Hashtable却不可以存储。究竟是为什么？下面看一下源代码：
HashMap.class:
// 此处计算key的hash值时，会判断是否为null，如果是，则返回0，即key为null的键值对
// 的hash为0。因此一个hashmap对象只会存储一个key为null的键值对，因为它们的hash值都相同。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 将键值对放入table中时，不会校验value是否为null。因此一个hashmap对象可以存储
// 多个value为null的键值对
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}Hashtable.class:
public synchronized V put(K key, V value) {
// 确保value不为空。这句代码过滤掉了所有value为null的键值对。因此Hashtable不能
// 存储value为null的键值对
if (value == null) {
throw new NullPointerException();
}
// 确保key在table数组中尚未存在。
Entry<?,?> tab[] = table;
int hash = key.hashCode(); //在此处计算key的hash值，如果此处key为null，则直接抛出空指针异常。
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}ConcurrentHashMap.class:
public V put(K key, V value) {
return putVal(key, value, false);
}
final V putVal(K key, V value, boolean onlyIfAbsent) {
// 在此处直接过滤掉key或value为null的情况
if (key == null || value == null) throw new NullPointerException();
// 另外其hash值采用了二次hash，使得hash值分布更均匀。
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}通过以上代码及注释分析可以总结如下：
1、 HashMap计算key的hash值时调用单独的方法，在该方法中会判断key是否为null，如果是则返回0；而Hashtable中则直接调用key的hashCode()方法，因此如果key为null，则抛出空指针异常。
2、 HashMap将键值对添加进数组时，不会主动判断value是否为null；而Hashtable则首先判断value是否为null。
3、以上原因主要是由于Hashtable继承自Dictionary，而HashMap继承自AbstractMap。
4、虽然ConcurrentHashMap也继承自AbstractMap，但是其也过滤掉了key或value为null的键值对。
public class Test {
public static void main(String[] args) {
Map<String, String> map = new HashMap<String, String>();//HashMap对象
Map<String, String> tableMap = new Hashtable<String, String>();//HashTable对象
map.put(null, null);
System.out.println("hashMap的[key]和[value]均可以为null:" + map.get(null));
try {
tableMap.put(null, "3");
System.out.println(tableMap.get(null));
} catch (Exception e) {
System.out.println("【ERROR】：hashTable的[key]不能为null");
}
try {
tableMap.put("3", null);
System.out.println(tableMap.get("3"));
} catch (Exception e) {
System.out.println("【ERROR】：hashTable的[value]不能为null");
}
}
}运行结果：
hashMap的[key]和[value]均可以为null:null
【ERROR】：hashTable的[key]不能为null
【ERROR】：hashTable的[value]不能为null
2 resize()
当元素向HashMap容器中添加元素的时候，会判断当前元素的个数，如果当前元素的个数大于等于阈值时，即当前数组table的长度*加载因子就要进行自动扩容。
由于HashMap的底层数据结构是“链表散列”，即数组和链表的组合，而数组是无法自动扩容的，所以只能是换一个更大的数组去装填以前的元素和将要添加的新元素
1.7
分析resize（）方法的源代码可以发现：在jdk1.7以前，resize（）方法传入的参数是新数组的容量，HashMap也不是无限能扩容的，1：方法中会首先判断扩容前的旧数组容量是否已经达到最大即2^30了，如果达到了就修改阈值为int的最大取值，这样以后就不会扩容了。
2：初始化一个新Entry数组；
3：计算rehash，判断扩容的时候是否需要重新计算hash值，将此值作为参数传入到transfer方法中；这个是和jdk1.8不同的一点，
4：通过transfer方法将旧数组中的元素复制到新数组，在这个方法中进行了包括释放就的Entry中的对象引用，该过程中如果需要重新计算hash值就重新计算，然后根据indexfor（）方法计算索引值。而索引值的计算方法为{ return h & (length-1) ；}即hashcode计算出的hash值和数组长度进行与运算。。。。。jdk1.7中重新插入到新数组的元素，如果原来一条链上的元素又被分配到同一条链上那么他们的顺序会发生倒置这个和1.8也不一样
1.8
1：resize方法源码融入了红黑树，本质和1.7区别不大,但是在插入元素的时候循环旧数组内的元素时会进行判断，如果是普通节点直接和1.7一样放置；如果是红黑树结构，就调用split（）方法进行拆分放置；如果是链表，则采用下面2中要分析的方式！！！！
2：在经过一次容量判断是否大于最大值之后在进行扩容，使用的扩容方法是2次幂的扩展，**所以元素要么在原来的位置，要么在原位置在移动2次幂的位置，**如下图：图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果。
因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：
因此，其实我们在扩容的时候不需要像jdk1.7那样重新计算hash，只要看看原hash值新增的那个bit位是1还是0就好了，是0的话索引没有变，是1的话索引变成“原索引+oldCap（旧数组大小）”，下图位resize（）方法示意图：
这个设计确实非常的巧妙，既省去了重新计算hash值的时间，也就是说1.8不用重新计算hash值而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。有一点注意区别，JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，因为他采用的是头插法，先拿出旧链表头元素。但是从上图可以看出**，JDK1.8不会倒置，采用的尾插法。**
3 jDK8中HashMap链表转红黑树的阈值为什么选8？为什么用红黑树做优化？
在平常我们用HashMap的时候，HashMap里面存储的key是具有良好的hash算法的key（比如String、Integer等包装类），冲突几率自然微乎其微，此时链表几乎不会转化为红黑树，但是当key为我们自定义的对象时，我们可能采用了不好的hash算法，使HashMap中key的冲突率极高，但是这时HashMap为了保证高速的查找效率，就引入了红黑树来优化查询了。
(翻译过来大概的意思是：理想情况下使用随机的哈希码，容器中节点分布在hash桶中的频率遵循泊松分布(具体可以查看http://en.wikipedia.org/wiki/Poisson_distribution)，按照泊松分布的计算公式计算出了桶中元素个数和概率的对照表，可以看到链表中元素个数为8时的概率已经非常小，再多的就更少了，所以原作者在选择链表元素个数时选择了8，是根据概率统计而选择的。)
通过源码我们得知HashMap源码作者通过泊松分布算出，当桶中结点个数为8时，出现的几率是亿分之6的，因此常见的情况是桶中个数小于8的情况，此时链表的查询性能和红黑树相差不多，因为转化为树还需要时间和空间，所以此时没有转化成树的必要。
泊松分布的参数λ是单位时间(或单位面积)内随机事件的平均发生次数。 泊松分布适合于描述单位时间内随机事件发生的次数。
既然个数为8时发生的几率这么低，我们为什么还要当链表个数大于8时来树化来优化这几乎不会发生的场景呢？
首先我们要知道亿分之6这个几乎不可能的概率是建立在什么情况下的 答案是：建立在良好的hash算法情况下，例如String，Integer等包装类的hash算法、如果一旦发生桶中元素大于8，说明是不正常情况，可能采用了冲突较大的hash算法，此时桶中个数出现超过8的概率是非常大的，可能有n个key冲突在同一个桶中，此时再看链表的平均查询复杂度和红黑树的时间复杂度，就知道为什么要引入红黑树了，
举个例子，若hash算法写的不好，一个桶中冲突1024个key，使用链表平均需要查询512次，但是红黑树仅仅10次，红黑树的引入保证了在大量hash冲突的情况下，HashMap还具有良好的查询性能
什么时候转成链表
长度为8的时候，平均查找长度为3，如果继续使用链表，平均查找长度为8/2=4，这才有转换为树的必要。链表长度如果是小于等于6，6/2=3，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。
于等于6时，树结构还原成链表。
泊松分布
4 平均查找长度详解
1.顺序查找：
从表的一端开始，顺序扫描线性表，依次将扫描到的节点关键字和给定值k相比较。
等概率条件下...平均查找长度：ASL = (n+....+2+1)/n= (n+1)/2。
2.二分法查找：
前提是线性表是有序表。假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较，如果当前位置值等于x，则查找成功；若x小于当前位置值，则在数列的前半段中查找；若x大于当前位置值则在数列的后半段中继续查找，直到找到为止。
在等概率条件下...平均查找长度：ASL =（1/n）* ( j * 2^(j-1) )(j是从1到h)，ASL = log2(n+1)-1。
原因：用二叉树来描述，树的高度d与节点树的关系为：n=(1+2+4+...... 2^(d-1))=2^d - 1；所以d = log2(n+1)，每一层只需要比较一次，所以最多需要比较log2(n+1)次。
3.分块查找：
又称索引顺序查找，由分块有序（每一块中的关键字不一定有序，但是前一块中的最大关键字必须小于后一块中的最小关键字，即分块有序。）的索引表和线性表组成。例如把r【1....n】分为 b 块，则前 b-1 块节点数为 s = 【n/b】，最后一块允许小于或等于s。索引表是一个递增有序表。
平均查找长度分为两部分，索引表的查找+块内的查找。（索引表能够用二分法和顺序查找，块内无序，所以只能用顺序查找）
如果以二分查找来确定块，则 ASL = log2(b+1)-1 + (s+1)/2。
如果以顺序查找来确定块，则 ASL = (b+1)/2 + (s+1)/2。
如果以哈希查找来确定块，则ASL=1 + (s+1)/2。
5 HashMap的get()过程
HashMap::getNode的流程是:
.1 通过 hash & (table.length - 1)获取该key对应的数据节点的hash槽;
.2 判断首节点是否为空, 为空则直接返回空;
.3 再判断首节点.key 是否和目标值相同, 相同则直接返回(首节点不用区分链表还是红黑树);
.4 首节点.next为空, 则直接返回空;
.5 首节点是树形节点, 则进入红黑树数的取值流程, 并返回结果;
.6 进入链表的取值流程, 并返回结果;
我们先来看简单的链表取值流程:
京公网安备 11010502036488号