hashmap源码

hashMap概览

1. hashmap的数据结构包括了初始数组，链表，红黑树
2. 插入数据的时候使用pos=key%size来进行插入数据
3. 当两个或者以上的key的key相同且key值不同的时候（发生冲突），就会挂在数组初始位置的链表后
4. 当某个节点后出现过多的链表节点的时候，就会转换成红黑树以提高效率

hashmap的数据结构包括了初始数组、链表、红黑树

//hashmap的构造public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; //DEFAULT_LOAD_FACTOR默认为0.75，此处构造只设置了默认加载因子一个属性}

put方法

  public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}//hash(key):默认生成的hash值
//此处key调用的hashcode()方法是本地方法涉及底层static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

// Callbacks to allow LinkedHashMap post-actions
//这个三个方法都是为了继承HashMap的LinkedHashMap类服务的。
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }//LinkedHashMap 是 HashMap 的一个子类，它保留插入的顺序，如果需要输出的顺序和输入时的相同，那么就选用 LinkedHashMap。LinkedHashMap中被覆盖的afterNodeInsertion方法，用来回调移除最早放入Map的对象
void afterNodeInsertion(boolean evict) { // possibly remove eldestLinkedHashMap.Entry<K,V> first;if (evict && (first = head) != null && removeEldestEntry(first)) {K key = first.key;removeNode(hash(key), key, null, false, true);}
}

hash冲突解决

 static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

扩容

//先判断是否大于阈值如果是调研resize()方法else if (s > threshold)；final Node<K,V>[] resize() {Node<K,V>[] oldTab = table; //table等于16int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;  //threshold等于12int newCap, newThr = 0;if (oldCap > 0) {if (oldCap >= MAXIMUM_CAPACITY) { // MAXIMUM_CAPACITY 为1左移30位threshold = Integer.MAX_VALUE;return oldTab;}else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && //将容量扩增一倍oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;else {               // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr; //将新的threshold赋给threshold@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab; //将新生成的容量空间赋给tableif (oldTab != null) {for (int j = 0; j < oldCap; ++j) {Node<K,V> e;if ((e = oldTab[j]) != null) {oldTab[j] = null;if (e.next == null)  //如果为空表示只有数组没有链表newTab[e.hash & (newCap - 1)] = e; //进行与运算获取它的新位置else if (e instanceof TreeNode)((TreeNode<K,V>)e).split(this, newTab, j, oldCap);// 如果是树形节点就将其进行拆分else { // preserve order 单链表Node<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);if (loTail != null) {loTail.next = null;newTab[j] = loHead;}if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;}

get方法

 final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;if ((tab = table) != null && (n = tab.length) > 0 && //判断是否为空或者大于零，如果成立表示节点还没有创建(first = tab[(n - 1) & hash]) != null) { //比较hash值如果相等就直接返回if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;if ((e = first.next) != null) { //判断next值是否为空if (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key); //按树形节点去查询返回结果do {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))) //单链表遍历比较hash值和keyreturn e;} while ((e = e.next) != null);}}return null;}

remove方法

map序列化

  private void writeObject(java.io.ObjectOutputStream s)throws IOException {int buckets = capacity();// Write out the threshold, loadfactor, and any hidden stuffs.defaultWriteObject();s.writeInt(buckets);//写入初始容量大小s.writeInt(size); //写入hashmap节点的数量internalWriteEntries(s);}

反序列化

 private void readObject(java.io.ObjectInputStream s)throws IOException, ClassNotFoundException {// Read in the threshold (ignored), loadfactor, and any hidden stuffs.defaultReadObject();reinitialize();//初始化if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new InvalidObjectException("Illegal load factor: " +loadFactor);s.readInt();                // Read and ignore number of bucketsint mappings = s.readInt(); // Read number of mappings (size)if (mappings < 0)throw new InvalidObjectException("Illegal mappings count: " +mappings);else if (mappings > 0) { // (if zero, use defaults)// Size the table using given load factor only if within// range of 0.25...4.0float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f);float fc = (float)mappings / lf + 1.0f;int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ?DEFAULT_INITIAL_CAPACITY :(fc >= MAXIMUM_CAPACITY) ?MAXIMUM_CAPACITY :tableSizeFor((int)fc));float ft = (float)cap * lf;threshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ?(int)ft : Integer.MAX_VALUE);// Check Map.Entry[].class since it's the nearest public type to// what we're actually creating.SharedSecrets.getJavaOISAccess().checkArray(s, Map.Entry[].class, cap);@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] tab = (Node<K,V>[])new Node[cap];table = tab;// Read the keys and values, and put the mappings in the HashMapfor (int i = 0; i < mappings; i++) {@SuppressWarnings("unchecked")K key = (K) s.readObject();@SuppressWarnings("unchecked")V value = (V) s.readObject();putVal(hash(key), key, value, false, false); //执行插入动作}}}

总结：

1. hashmap的数据结构包括了初始数组，链表，红黑树
2. 数组容量是2的倍数：提高运算速度，增加散列度，降低冲突，减少内存碎片
3. hash函数与pos定位：hashcode的高16位与低16位进行异或求模，增加了散列度降低了冲突
4. 插入冲突：通过单链表解决冲突，如果链表长度超过（TREEIFY_THRESHOLD=8），进行单链表和红黑树的转换以提高查询速度
5. 扩容：扩容的条件：实际节点数大于等于容量的四分之三；扩容后数据排布：要么是原下标的位置；要么是原下标+原容量的位置
6. 序列化：只存储了数组的容量、实际节点数量和各个节点的key、value值