HashMap学习笔记

1、HashMap底层数据结构

底层数据结构： 数组+链表+红黑树（JDK1.8以后）

1.1 数组

数组： 使用一段连续的存储单元存储数据，对于指定下标的查找，时间复杂度为O(1)，对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度为O(n)。所以说虽然数组读取速度快，但是前提是需要知道数组对应元素的下标索引。

1.2 链表

链表： 对链表的新增，删除操作在查找到操作位置后，只需要处理节点间的引用即可，时间复杂度为O(1)，查找操作需要遍历链表中的所有节点逐一进行比对，时间复杂度为O(n)。

1.3 红黑树

红黑树： 一种接近平衡二叉搜索树，在每个节点上增加一个存储为表示节点的颜色，可以是Red或Black，通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的， 支持查找、插入、删除等操作，其平均时间复杂度最坏为O(logn<n) 红黑树的5个特性： 1. 每个节点要么是红色，要么是黑色。 2. 根结点事黑色。 3. 每个叶结点（叶结点即指树尾端null指针或null结点）都是黑色的。 4. 如果一个结点是红色，那么它的两个子结点都是黑色。 5. 对于任意结点而言，其到叶结点树尾端null指针的每条路径都包含相同数量的黑结点。

2、HashMap底层存储原理

2.1 HashMap的key为空时

HashMap中的key允许为空，当key为空的时候会单独开辟一个空间用于存储当前的值。具体实现 // JDK1.8之后HashMap中的寻址算法，其算法规则效果等同于 hash % length但是性能要更好，另外也是由于这个原因所以HashMap初始化的时候数组长度需要为2的n次方，例如HashMap创建时默认的数组长度为16。 hash & (length - 1) // JDK1.8之后HashMap中的Hash算法的优化(h = key.hashCode()) ^ (h >>> 16) static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

2.2 HashMap取值原理

HashMap的取值原理：由于HashMap底层是由数组 + 链表 + 红黑树组成，因此根据key取值的时候并不仅仅只比较key在HashMap底层数组对应的下标，还会比较下标对应链表/红黑树每个对象中的hashCode值，只有链表/红黑树中的对象的hashCode值与对应key的hashCode相等才能确定当前key对应的对象。底层源码实现： if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { 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)))) return e; } while ((e = e.next) != null); } }

2.3 HashMap链表与红黑树的转换

HashMap底层由链表转成红黑树的阈值为：8，之所以不在刚开始就使用红黑树而使用链表，是因为链表的插入性能高于红黑树。具体底层源码实现 static final int TREEIFY_THRESHOLD = 8; 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; }

3、模拟HashMap自定义Map类

Map接口

package com.xununan.www.map; /** * @packageName com.xununan.www.map * @className Map * @description: 自定义Map * @author: xu * @create: 2020/04/26 22:25 */ public interface Map<K, V> { public V put(K k, V v); public V get(K k); public int size(); public interface Entry<K, V> { public K getKey(); public V getValue(); } }

Map实现：数组 + 链表的方式

package com.xununan.www.map; /** * @packageName com.xununan.www.map * @className MyMap * @description: 自定义Map类 * @author: xu * @create: 2020/04/26 22:27 */ public class MyMap<K, V> implements Map<K, V> { private Entry[] table = null; private int size = 0; public MyMap() { table = new Entry[16]; } /** * 功能描述：put <br> * 1. key查询hashCode * 2. hashCode取模获得下标 * 3. 根据下标找到数组对象 * 4. 是否为空进行存储 * @param k * @param v * @return V * * @Author xu * @Date 2020-04-26 22:32 * @Version 1.0.0 */ @Override public V put(K k, V v) { int index = this.hash(k); Entry<K, V> entry = table[index]; if (entry == null) { table[index] = new Entry(k, v, k.hashCode(), null); size ++ ; } else { table[index] = new Entry(k, v, k.hashCode(), entry); } return (V) table[index].getValue(); } private int hash(K k) { return Math.abs(k == null ? 0 : k.hashCode() % 16); } /** * 功能描述：get <br> * 1. key找到index * 2. 数组位置 * 3. 判断当前对象是否有值，有的话比较对象的hashcode * 4. 如果当前hashcode值详单则直接返回如果不相等则继续比较下一个对象的hashcode * @param k * @return V * * @Author xu * @Date 2020-04-26 22:43 * @Version 1.0.0 */ @Override public V get(K k) { int index = this.hash(k); Entry<K,V> entry = table[index]; if (entry == null) { return null; } do { if (k.hashCode() == entry.hashCode) { return entry.getValue(); } else { entry = entry.next; } } while (entry != null); return null; // return this.find(index, entry); } private V find(int index, Entry<K,V> entry) { if (entry.hashCode == index) { return entry.getValue(); } else { if (entry.next != null) { return find(index, entry.next); } else { return null; } } } @Override public int size() { return size; } class Entry<K, V> implements Map.Entry<K, V> { K k; V v; int hashCode; Entry<K, V> next; public Entry(K k, V v, int hashCode, Entry<K, V> next) { this.k = k; this.v = v; this.hashCode = hashCode; this.next = next; } @Override public K getKey() { return k; } @Override public V getValue() { return v; } } }

以上为个人总结的一些笔记，若有雷同纯属巧合，若有错误欢迎指出，谢谢！