HashMap的内部数据结构
HashMap 在1.7之前的数据结构为 数组 + 链表，如图所示：
hashmap7.png
HashMap 概念讲解：
-
size 表示HashMap中存放KV的数量（为链表和树中的KV的总和）
-
capacity 译为容量。capacity就是指HashMap中桶的数量（Table的长度）。默认值为16。容量都是2的幂。
-
loadFactor 译为装载因子。装载因子用来衡量HashMap满的程度。loadFactor的默认值为0.75f。计算HashMap的实时装载因子的方法为：size/capacity。
-
threshold 译为阈值 threshold=capacity*loadFactor
-
HashMap数组：transient Entry[] table
-
数组默认长度：static final int DEFAULT_INITIAL_CAPACITY = 1 << 4
-
数组最大长度：static final int MAXIMUM_CAPACITY = 1 << 30
-
默认加载因子：static final float DEFAULT_LOAD_FACTOR = 0.75f
1.8 之后数据结构改为 数组 + 链表 + 红黑树，如图所示：
hashmap8.jpg
HashMap的数据插入原理
jdk1.7 的插入原理如下：
hashmap7_put.png
java 1.8的插入原理如下：
hashmap8_put流程图.png
**hash冲突你还知道哪些解决办法 **
比较出名的有四种(1)开放定址法(2)链地址法(3)再哈希法(4)公共溢出区域法
- 开放定址法
线性探测法、 平方探测法、 双散列函数探查法
- 链地址法
HashMap 1.7 采用这种方法
- 再哈希法
就是同时构造多个不同的哈希函数：
Hi = RHi(key) i= 1,2,3 ... k;
当H1 = RH1(key) 发生冲突时，再用H2 = RH2(key) 进行计算，直到冲突不再产生，这种方法不易产生聚集，但是增加了计算时间。
- 公共溢出区域法
将哈希表分为公共表和溢出表，当溢出发生时，将所有溢出数据统一放到溢出区。
HashMap的哈希函数怎么设计的吗？
以下为jdk1.8里的hash方法。1.7的就不看了。 (现在问的也少了)
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
hash函数是先拿到通过key 的hashcode，是32位的int值，然后让hashcode的高16位和低16位进行异或操作。
为什么采用hashcode的高16位和低16位异或能降低hash碰撞？hash函数能不能直接用key的hashcode？
这个也叫扰动函数， HashMap 这么设计有两点原因：
- 一定要尽可能降低hash碰撞，越分散越好；
- 算法一定要尽可能高效，因为这是高频操作, 因此采用位运算；
key.hashCode()函数调用的是key键值类型自带的哈希函数（Object.hashCode() 是一个native的方法），返回int型散列值。 int值范围为-21474836482147483647[-2^312^31-1]，前后加起来大概40亿的映射空间。只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个40亿长度的数组，内存是放不下的。如果HashMap数组的初始大小才16，用之前需要对数组的长度取模运算（ hash%length ），余数就是数组下标。
但是，大家都知道这种运算不如位移运算快。因此，源码中做了优化hash&(length-1)。也就是说hash%length==hash&(length-1)
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
与1.7 对应的函数是：
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
这也正好解释了为什么HashMap的数组长度要取2的整数幂。因为这样（数组长度-1）正好相当于一个“低位掩码”。 &操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。以初始长度16为例，16-1=15。2进制表示是00000000 00000000 00001111。和某散列值做&操作如下，结果就是截取了最低的四位值。
10100101 11000100 00100101
& 00000000 00000000 00001111
----------------------------------
00000000 00000000 00000101 //高位全部归零，只保留末四位
但这时候问题就来了，这样就算我的散列值分布再松散，要是只取最后几位的话，碰撞也会很严重。如果散列本身做得不好，分布上成等差数列，如果正好让最后几个低位呈现规律性重复，那么碰撞次数就多了起来。
"asdfggggasdfasdf"的hashcode值为 11011010011011100011011001011100 如下所示 (HashMap() default length is 16 )：
h = h.hashCode(): 1101 1010 0110 1110 0011 0110 0101 1100
(h >>> 16) 无符号右移16位： 0000 0000 0000 0000 1101 1010 0110 1110 0011 0110 0101 1100
hash= h^(h >>> 16): 1101 1010 0110 1110 1110 1100 0011 0010
2^4 - 1=15 (length-1): 0000 0000 0000 0000 0000 0000 0000 1111
(n - 1) & hash : 0000 0000 0000 0000 0000 0000 0000 0010
index = 2 : 0010
右位移16位，正好是32bit的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。
最后我们来看一下Peter Lawley的一篇专栏文章《An introduction to optimising a hashing strategy》里的的一个实验：他随机选取了352个字符串，在他们散列值完全没有冲突的前提下，对它们做低位掩码，取数组下标。
扰动函数.png
结果显示，当HashMap数组长度为512的时候，也就是用掩码取低9位的时候，在没有扰动函数的情况下，发生了103次碰撞，接近30%。而在使用了扰动函数之后只有92次碰撞。碰撞减少了将近10%。看来扰动函数确实还是有功效的。
另外Java1.8相比1.7做了调整，1.7做了四次移位和四次异或，但明显Java 8觉得扰动做一次就够了，做4次的话，多了可能边际效用也不大，所谓为了效率考虑就改成一次了。
下面是1.7的hash代码：
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
String中hashcode的实现?
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
String类中的hashCode计算方法还是比较简单的，就是以31为权，每一位为字符的ASCII值进行运算，用自然溢出来等效取模。
哈希计算公式可以计为s[0]31^(n-1) + s[1]31^(n-2) + … + s[n-1]
那为什么以31为质数呢?
主要是因为31是一个奇质数，所以31i=32i-i=(i<<5)-i，这种位移与减法结合的计算相比一般的运算快很多。
**为什么在解决hash冲突的时候，不直接用红黑树?而选择先用链表，再转红黑树? **
因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡，而单链表不需要。
当元素小于8个当时候，此时做查询操作，链表结构已经能保证查询性能。当元素大于8个的时候，此时需要红黑树来加快查询速度，但是新增节点的效率变慢了。
因此，如果一开始就用红黑树结构，元素太少，新增效率又比较慢，无疑这是浪费性能的。
**那为什么阀值是8呢? **
不知道。。。。。。。
当链表转为红黑树后，什么时候退化为链表?
为6的时候退转为链表。中间有个差值7可以防止链表和树之间频繁的转换。假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。
**健可以为Null值么? **
必须可以，key为null的时候，hash算法最后的值以0来计算，也就是放在数组的第一个位置。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
你一般用什么作为HashMap的key?
一般用Integer、String这种不可变类当HashMap当key，而且String最为常用。
-
因为字符串是不可变的，所以在它创建的时候hashcode就被缓存了，不需要重新计算。这就使得字符串很适合作为Map中的键，字符串的处理速度要快过其它的键对象。这就是HashMap中的键往往都使用字符串。
-
因为获取对象的时候要用到equals()和hashCode()方法，那么键对象正确的重写这两个方法是非常重要的,这些类已经很规范的覆写了hashCode()以及equals()方法。
用可变类当HashMap的key有什么问题?
hashcode可能发生改变，导致put进去的值，无法get出，如下所示 :
@Test
public void testHashMapGet(){
HashMap<List<String>, Object> changeMap = new HashMap<>();
List<String> list = new ArrayList<>();
list.add("hello");
Object objectValue = new Object();
changeMap.put(list, objectValue);
Assert.assertNotNull(changeMap.get(list)); // true
list.add("hello world");//hashcode发生了改变
Assert.assertNotNull(changeMap.get(list)); // false
}
HashMap在并发编程环境下有什么问题啊?
1.7 的时候，HashMap 在多并发环境下，有可能遇到如下问题：
- 多线程扩容，引起的死循环问题
- 多线程put的时候可能导致元素丢失
- put非null元素后get出来的却是null
知道jdk1.8中hashmap改了啥么?
- 由数组+链表的结构改为数组+链表+红黑树。
- 优化了高位运算的hash算法：h^(h>>>16)
- 扩容后，元素要么是在原位置，要么是在原位置再移动2次幂的位置，且链表顺序不变。
最后一条是重点，因为最后一条的变动，hashmap在1.8中，不会在出现死循环问题。
平常怎么解决这个线程不安全的问题
Java中有HashTable、Collections.synchronizedMap、以及ConcurrentHashMap可以实现线程安全的Map。
HashTable是直接在操作方法上加synchronized关键字，锁住整个数组，粒度比较大，Collections.synchronizedMap是使用Collections集合工具的内部类，通过传入Map封装出一个SynchronizedMap对象，内部定义了一个对象锁，方法内通过对象锁实现；ConcurrentHashMap使用分段锁，降低了锁粒度，让并发度大大提高。
那你知道ConcurrentHashMap的分段锁的实现原理吗
ConcurrentHashMap成员变量使用volatile 修饰，免除了指令重排序，同时保证内存可见性，另外使用CAS操作和synchronized结合实现赋值操作，多线程操作只会锁住当前操作索引的节点。
如下图，线程A锁住A节点所在链表，线程B锁住B节点所在链表，操作互不干涉。
HashMap内部节点是有序的吗？
是无序的，根据hash值随机插入
那有没有有序的Map？
LinkedHashMap 和 TreeMap
LinkedHashMap怎么实现有序的？
LinkedHashMap内部维护了一个单链表，有头尾节点，同时LinkedHashMap节点Entry内部除了继承HashMap的Node属性，还有before 和 after用于标识前置节点和后置节点。可以实现按插入的顺序或访问顺序排序。
/**
* The head (eldest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> head;
/**
* The tail (youngest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> tail;
/**
* The iteration ordering method for this linked hash map: <tt>true</tt>
* for access-order, <tt>false</tt> for insertion-order.
*
* @serial
*/
final boolean accessOrder;
// internal utilities
// link at the end of list
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
/**
* HashMap.Node subclass for normal LinkedHashMap entries.
*/
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
@Test
public void testLinkedHashMap(){
Map<String, String> map = new LinkedHashMap<String, String>();
map.put("11111", "Bern");
map.put("222", "的");
map.put("3333", "简书");
map.forEach((k,v)->System.out.println("Item: [" + k + "] value: [" + v + "]"));
}
@Test
public void testHashMap(){
Map<String, String> map = new HashMap<String, String>();
map.put("11111", "Bern");
map.put("222", "的");
map.put("3333", "简书");
map.forEach((k,v)->System.out.println("Item: [" + k + "] value: [" + v + "]"));
}
//testLinkedHashMap output
Item: [11111] value: [Bern]
Item: [222] value: [的]
Item: [3333] value: [简书]
//testHashMap output
Item: [222] value: [的]
Item: [3333] value: [简书]
Item: [11111] value: [Bern]
TreeMap怎么实现有序的？
TreeMap是按照Key的自然顺序或者Comprator的顺序进行排序，内部是通过红黑树来实现。所以要么key所属的类实现Comparable接口，或者自定义一个实现了Comparator接口的比较器，传给TreeMap用户key的比较。
前面提到jdk1.7在并发编程环境下会出现死循环，能具体讲讲吗？
有点口渴，我们下一章节详细介绍。
网友评论