面试题：
- hashmap谈一谈
- hashmap的set和get的时间复杂度是多少？为什么是O(1), hashmap 在jdk1.8是线程安全的吗？
为什么是线程安全的？concureenthashmap了解吗？他是如何实现线程安全的？- HashMap
查询时间复杂度，有冲突呢
HashCode 函数设计
如何用HashMap 加锁 保证线程安全，不可以用JUC下类- HashMap 的插入时间复杂度
- Java中HashMap与HashTable区别
- Java中HashMap底层数据结构
- hashmap底层结构，红黑树什么时候退化，如何扩容
- hashmap的默认数组长度是多少，hashmap中的取余操作是怎么做的
- HashMap为什么是非线程安全的
- HashMap有了解吗？HashMap的时间复杂度？HashMap中Hash冲突是怎么解决的？链表的上一级结构是什么？Java8中的HashMap有什么变化？红黑树需要比较大小才能进行插入，是依据什么进行比较的？其他Hash冲突解决方式？
- hashmap如何解决hash冲突，为什么hashmap中的链表需要转成红黑树？
- hashmap扩容时每个entry需要再计算一次hash吗？
- hashmap的数组长度为什么要保证是2的幂？
- hashmap什么时候会触发扩容？
0、1.7的实现由数组加上链表实现
1、Entry结构
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
table = new Entry[capacity];
table
2、public V put(K key, V value)操作
1、首先判断table是否为空，如果空，就去创建size为capacity的Entry数；
2、不为空，判断key是否为null，如果为null，就putForNullKey(value)；
3、如果不为null，就计算key的hash值，再根据hash值和 table.length计算对应在数组中的下标；
4、根据下标去看对应的链上是否有key相同的节点，如果有就把该节点的值覆盖掉，返回旧的值；
5、如果对应下标为null，或者找不到相同key的节点，就使用头插法，将新的new Entry<>(hash, key, value, e)，放在table[bucketIndex]上。
6、5中还涉及到table扩容的问题。
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
1、触发扩容
如果size 的大小大于等于了capacity * loadFactor ，就会触发扩容，容量变为原来的两倍；
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
if ((size >= threshold) && (null != table[bucketIndex]))
2、hashmap扩容时每个entry需要再计算一次hash吗？
不是，首先key为null的entry就不需要重新计算，其次rehash几乎不会触发
3、Hashmap的默认数组长度是多少，hashmap中的取余操作是怎么做的
默认16, 取余h & (length-1)
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
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);
}
