HashMap的存储结构
JDK 1.8之前
在JDK 1.7,HashMap采用的是数组+链表(头插法) 的存储结构。HashMap通过key的hashCode经过hash方法处理过后得到hash值,然后通过 (n - 1) & hash 判断当前元素存放的位置(n指的是数组的长度),如果当前位置存在元素的话,就判断该元素与要存在的元素的hash值以及key是否相同,如果相同的话,直接覆盖,不相同就通过拉链法解决冲突。JDK 1.8之前的hash方法如下:
1 2 3 4 static int hash (int h) { h ^= (h >>> 20 ) ^ (h >>> 12 ); return h ^ (h >>> 7 ) ^ (h >>> 4 ); }
存储结构如下:
所谓 “拉链法” 就是将链表和数组相结合。也就是说创建⼀个链表数组,数组中每⼀格就是⼀个链表。若遇到哈希冲突,则将冲突的值加到链表中即可
JDK 1.8
JDK 1.8之前的HashMapHashMap采用的是数组+链表(头插法)的存储结构,在链表很长时查询效率明显降低o(n),所以JDK 1.8做了很多优化采用数组+链表(尾插法)+红黑树 的存储结构。红黑树的查询时间复杂度是o(log n)。当链表长度大于阈值(默认8)时,如果当前数组的长度小于阈值(默认64),那么会先进行数组扩容,否则会把链表转化为红黑树,以提高查询效率。当红黑树上的元素个数减少到阈值(默认6)时,会再转为链表。JDK 1.8的hash方法如下:
1 2 3 4 5 6 7 static final int hash (Object key) { int h; return (key == null ) ? 0 : (h = key.hashCode()) ^ (h >>> 16 ); }
相对于JDK 1.7的hash方法的性能会稍微差一点点,因为扰动了4次。
存储结构如下:
常用变量
在 HashMap源码中,比较重要的常用变量,主要有以下这些。还有两个内部类来表示普通链表的节点和红黑树节点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 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 int TREEIFY_THRESHOLD = 8 ;static final int UNTREEIFY_THRESHOLD = 6 ;static final int MIN_TREEIFY_CAPACITY = 64 ;transient Node<K,V>[] table;transient Set<Map.Entry<K,V>> entrySet;transient int size;transient int modCount;int threshold;final float loadFactor; static class Node <K,V> implements Map .Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) { this .hash = hash; this .key = key; this .value = value; this .next = next; } } static final class TreeNode <K,V> extends LinkedHashMap .Entry<K,V> { TreeNode<K,V> parent; TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; boolean red; TreeNode(int hash, K key, V val, Node<K,V> next) { super (hash, key, val, next); } }
小结
HashMap是无序且线程不安全的
HashMap可以存null键和值,key重复会被覆盖,value可以重复
HashMap每次是成倍扩容,且长度都是2的幂次方
这是为了尽量减少hash冲突考虑的。如果自己传的长度到HashMap构造方法,会返回大于等于参数的最小2次幂。
1 HashMap<String,String> map = new HashMap <>(13 );
JDK 1.7的HashMap在多线程环境下可能会出现链表死循环
原因是采用头插法,多线程推荐使用ConcurrentHashMap(JDK 1.7使用Segment,JDK 1.8使用synchronized和CAS,synchronized只锁定当前链表或红黑树的首节点,效率提升n倍)
参考链接