JDK1.8 HashMap 源码分析详解

以键值对的形式存储，是基于Map接口的实现,可以接收null的键值，不保证有序（比如插入顺序），存储着Entry(hash, key, value, next)对象。

二、示例 public static void main(String[] args){ Map<String, Integer> map = new HashMap<String, Integer>(); map.put("上海", 1); map.put("北京", 2); map.put("广州", 3); map.put("天津", 4); map.put("重庆", 5); for(Map.Entry<String, Integer> entry : map.entrySet()) { System.out.println(entry.getKey() + ": " + entry.getValue()); } }

IntelliJ IDEA 调试，通过Variables我们能看到这样的储存方式：

三、HashMap存储的数据结构 3.1 数据结构

通过示例调试可以总结出HashMap示例存储的数据结构：

3.2 数据结构核心代码 3.2.1 table transient Node<K,V>[] table; 3.2.2 Node

Node是HashMap的一个内部类，单向链表实现方式

static class Node<K,V> implements Map.Entry<K,V> { final int hash; //用来定位数组索引位置 final K key; V value; Node<K,V> next; //链表的下一个node Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } } 3.2.3 TreeNode 红黑树 static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // red-black tree links TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; // needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node<K,V> next) { super(hash, key, val, next); } //返回当前节点的根节点 final TreeNode<K,V> root() { for (TreeNode<K,V> r = this, p;;) { if ((p = r.parent) == null) return r; r = p; } } 以下省略... ... } 四、HashMap主要属性 //默认初始容量为16，必须为2的幂 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //最大容量为2的30次方 static final int MAXIMUM_CAPACITY = 1 << 30; ////默认加载因子0.75,当HashMap的数据大小>=容量*加载因子时，HashMap会将容量扩容 static final float DEFAULT_LOAD_FACTOR = 0.75f; //链表长度大于8时，将链表转化为红黑树 static final int TREEIFY_THRESHOLD = 8; //如果发现链表长度小于 6，则会将红黑树重新退化为链表 static final int UNTREEIFY_THRESHOLD = 6; //转变成树之前进行一次判断，只有键值对数量大于64才会发生转换。这是为了避免在哈希表建立初期，多个键值对恰好被放入了同一个链表中而导致不必要的转化。 static final int MIN_TREEIFY_CAPACITY = 64; //MIN_TREEIFY_CAPACITY>= 4 * TREEIFY_THRESHOLD //下次扩容的临界值，size>=threshold就会扩容,threshold＝容量*加载因子 int threshold; final float loadFactor; // 修改次数 transient int modCount; 五、HashMap的部分源码分析