HashMap小结

HashMap小结

1、HashMap基本特点2、HashMap实现方法3.Hash的底层实现

3.1 底层数据结构3.2 jdk1.8之前HashMap存在的问题3.3 Hash包含的重要变量 4.put方法分析5.常见问题

5.1加载因子为什么默认值为0.75f？5.2HashMap如何实现序列化和反序列化（io）5.3 HashMap和Hashtable的区别5.4 HashMap和ConcurrentHashMap区别5.5 HashMap 的长度为什么是 2 的幂次方5.6 如何决定使用HashMap还是TreeMap? 1、HashMap基本特点 HashMap实现了Map接口。HashMap允许有null键和null值。HashMap键不能重复，null键会按照普通键对待。如果键重复，会按照覆盖重复的键。HashMap是无序的。Map接口提供三种collection视图，允许以键集，值集或者键-值映射关系集的形式查看某个映射的内容。映射的顺序定于迭代器在映射的collection视图上返回其元素的顺序。某些映射实现可明确保证其顺序，如TreeMap类。另一些映射实现则不保证顺序，如HashMap。 2、HashMap实现方法 方法说明Object put(Object key,Object value)将互相关联的一组键/值对放入该映像Object remove(Object key)从映射中删除与key相关的映射void clear()从映像中删除所有映射Object get(Object key)获得与关键字key相关的值boolean containsKey(Object Key)判断映像中是否存在关键字keyint size()返回当前映像中映射的数量boolean isEmpty()判断映像是否为空Set keySet()返回映像中所有关键字的视图集Collection values()返回映像中所有值的视图集Set entrySet()返回Map.Entry对象的视图集，即印象中的关键字/值对3.Hash的底层实现

基于哈希表的Map接口实现。此实现提供所有可选的映射操作，并允许使用null值和null键。（除了非同步和允许使用的null之外，HashMap类与HashTable大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

3.1 底层数据结构

HashMap底层采用哈希表结构（数组+链表+红黑树）实现，结合了数组和链表的优点：
1、数组优点：通过数组下标可以快速实现对数组元素的访问，效率极高。
2、链表优点：插入或删除数据不需要移动元素，只需要修改节点引用，效率极高。

HashMap内部使用数组存储数据，数组中的每个元素类型为Node

static class Node implements Map.Entry { final int hash; final K key; V value; Node next; Node(int hash, K key, V value, Node 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; } }

Node包含了四个字段：hash，key,value,next,其中next表示链表的下一个节点。

3.2 jdk1.8之前HashMap存在的问题

HashMap通过Hash方法计算key的哈希码，然后通过（n-1）&hash公式（n为数组长度）得到key在数组中存放的下标。当两个key在数组中存放的下标一致时，数组将以链表的方式存储（哈希碰撞）。在链表中查找数据必须从第一个元素开始一层一层往下找，知道找到为止，所以当链表长度越来越长时，HashMap的效率越来越低。

解决思想：
加入红黑树的结构来实现HashMap。当链表中的元素超过8个，并且数组长度大于64时，会将链表转换为红黑树。
红黑树的节点使用TreeNode表示：

static final class TreeNode extends linkedHashMap.Entry { TreeNode parent; // red-black tree links TreeNode left; TreeNode right; TreeNode prev; // needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node next) { super(hash, key, val, next); } ..... }

3.3 Hash包含的重要变量

//默认数组初始化长度为16static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16//数组最大容量，2的30次幂，即1073741824 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; //链表转换为红黑树时，数组容量必须大于等于64 static final int MIN_TREEIFY_CAPACITY = 64; //HashMap里键值对的个数 transient int size; //扩容阈值：数组容量*加载因子 int threshold; //HashMap使用数组存放数据，数组元素类型为Node transient Node[] table; //加载因子 final float loadFactor;

4.put方法分析

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; //如果数组为null或者长度为0，则进行数组初始化操作 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //根据key的哈希值计算出数据插入数组的下标·位置 if ((p = tab[i = (n - 1) & hash]) == null) //如果改下标还没有元素，则直接创建Node对象，并插入 tab[i] = newNode(hash, key, value, null); else { Node e; K k; //如果目标位置key已经存在，则直接覆盖 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //如果目标位置key不存在，且节点为红黑树，则插入红黑树中 else if (p instanceof TreeNode) e = ((TreeNode)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); //如果链表长度大于等于8，则考虑转换为红黑树 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash);//转换为红黑树操作，内部还会判断数组长度是否小于64，如果是的化不转换 break; } //如果链表中已经存在该key的话，直接覆盖替换 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; }

put操作过程总结：
1.判断HashMap数组是否为空，是的话初始化数组（由此可见，在创建HashMap对象时，不会直接初始化数组）
2.通过（n-1）&hash计算key在数组中的存放索引
3.如果目标索引为空的话，则创建node对象存储
4.如果目标索引不为空，则分为下面3中情况
（1）key值相同，则覆盖原索引
（2）该节点时红黑树的话，执行红黑树插入操作
（3） 该节点类型是链表的话，遍历到最后一个元素尾部插入，如果中间遇到key相同的，则直接覆盖。如果链表长度大于等于8，数组长度大于等于64，则将链表转换为红黑树结构。
5.判断HashMap元素个数是否大于threshold（数组容量*加载因子），是的话，进行扩容操作（扩大2倍）

5.常见问题 5.1加载因子为什么默认值为0.75f？

扩容这个过程非常耗时，会影响程序性能。所以加载因子是基于容量和性能之间平衡的结果。
当加载因子过大时，扩容的占用就回贬低，但是哈希碰撞的几率增加，效率下降。
当加载因子过小时，容量占用变大。

5.2HashMap如何实现序列化和反序列化（io）

用于存储数据的table字段都使用transient修饰，通过transient修饰的字段在序列化时将被排除在外，那么HashMap在序列化后进行反序列化时，通过自定义方法来序列化和反序列化操作。
1.table一般不会存满，序列化table未使用的部分浪费时间和空间
2.同一个记住你支队在不同jvm下，在table存储的位置可能不同，那么反序列化时可能出错

5.3 HashMap和Hashtable的区别

同：HashMap 和 HashTable 都是基于哈希表实现的，其内部每个元素都是 key-value 键值对，HashMap 和 HashTable 都实现了 Map、Cloneable、Serializable 接口。
不同：
1.父类不同：HashMap 继承了 AbstractMap 类，而 HashTable 继承了 Dictionary 类。
2.空值不同：HashMap 允许空的 key 和 value 值，HashTable 不允许空的 key 和 value 值。HashMap 会把 Null key 当做普通的 key 对待。不允许 null key 重复。
3.安全性：HashMap线程不安全，HashTable线程安全。
4.性能：HashTable由于加了 synchronized 锁，操作较为耗时。
5.初始容量不同：HashTable 的初始长度是11，之后每次扩充容量变为之前的 2n+1(n为上一次的长度)，而 HashMap 的初始长度为16，之后每次扩充变为原来的两倍。创建时，如果给定了容量初始值，那么HashTable 会直接使用你给定的大小，而 HashMap 会将其扩充为2的幂次方大小。

5.4 HashMap和ConcurrentHashMap区别

HashMap线程不安全，ConcurrentHashMap是线程安全的。

5.5 HashMap 的长度为什么是 2 的幂次方

当数组长度不为2 的幂次方时，hash&（n-1）时，会产生大量重复数据，这样会增大 HashMap 碰撞的几率。

5.6 如何决定使用HashMap还是TreeMap?

如果你需要得到一个有序的结果时就应该使用TreeMap（因为HashMap中元素的排列顺序是不固定的）。除此之外，由于HashMap有更好的性能，所以大多不需要排序的时候我们会使用HashMap。