1. HashMap的结构和初始值：
- 主体结构为数组 Node<K,V>[] table，每个数组上存储的是单链表；
- 数组初始容量为16，负载因子0.75；
- 规定链表长度超过8，转成红黑树
2. HashMap插入流程
1610699244284.jpg
图片来自于《美团点评技术团队文章》
3. 哈希冲突是什么？怎么解决？
定义：
当我们进行put方法时，会根据Key的hash值，进过扰动算法后，和数组长度去进行位运算，得到该值在数组中存储位置的下标。也就有可能导致，不同的key计算出相同的下标，由此导致hash冲突。
如何解决：
1.采用链表的方法解决hash冲突。
- 将数组的长度定义为2的幂次方，可以最大限度的避免hash冲突
4. 为什么数组长度定义为2的幂次方？
- 为了尽可能避免hash冲突，我们应该将不同hash的key，尽可能分散在数组的每个下标，最直接的办法就是用hash值和数组长度取模；
- 而取模运算非常低效，位与运算（都为1才是1，否则为0）非常高效，且有如下等式 ：
hash % 2的n次方 = hash & (n-1)
因为一个数对2的n次方取模，就相当于该数右移n位，移出去的数就是余数。
就是说现在有一个转化方式，可以将模运算转位运算提高性能，前提是数组长度必须是2的幂次方，hashmap为了性能着想，果断采用。
5. 如果数组长度初始化不为2的幂次方会怎么样？
HashMap底层早有考虑。有如下方法，可以将用户设的任意数转为大于该任意数的，且最接近该数的2的幂次方：
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
即 7 -> 8, 12-> 16 , 20 -> 32
6.负载因子有何作用
极限值 = 数组长度 * 负载因子
当数组的使用超过极限值时，便进行扩容，扩容的容量为原来的2倍:
resize()方法中：
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
将原来的长度进行左移一位运算，相当于*2，HashMap中真是处处体现对性能的优化。
当负载因子过小，会导致稍有不慎就需要扩容，而扩容是耗时操作，即浪费内存，也消耗性能；
当负载因子过大，就会很难得扩容，大量的数据都会接在链表上，就会导致链表过长，这样搜索会变的耗时。
0.75是一个折中的数值。
7. 线程安全问题
HashMap是线程不安全的，有可能多个线程同时去修改某个值，就会导致数据不一致或数据污染。
而且，在多线程下操作 HashMap，由于存在扩容机制，当 HashMap 调用
resize()进行自动扩容时，可能会导致死循环的发生。
所以：如果有线程同步问题，建议使用ConcurrentHashMap，如果只在单线程，建议使用HashMap。至于HashTable，呵，明明三个人的电影，我却不能拥有姓名。
但是HashTable和HashMap的区别，是需要了解的。
除了红黑树，HashMap知识点应该都讲完了。如果被问到红黑树，那就投降吧。
网友评论