重点是这：hashMap：https://blog.****.net/u012512634/article/details/72

hash表：https://blog.****.net/xiaoxik/article/details/74926090

hash算法：https://blog.****.net/sinat_31011315/article/details/78699655

 

其中要注意的几个点:

Hash函数的构造方法（算的是hashcode）：

 通过hash公式算得index；

 

 

当容量不够的时候，会进行扩容：

 

arraylist每次是扩容1.5倍，HashMap是2倍

arraylist中实现的容量增加的方法；

 

 

当发生地址冲突的时候（不是容量不够的时候）:

1.。再哈希法，重新计算一次hash值，但好费时间

2.建立公共溢出区，新建一个哈希表来存放key值；

 以上是JDK1.7之前采用位桶+链表，缺点是：当冲突频繁发生时，查找时间复杂度变成了O(n)；

   JDK1.8采用位桶+链表/红黑树，当一个格子内的数据长度超过了8，就会转化为红黑树，这样查找时间变成了O(logn)；

 

 

hashMap的源码：

 

（不确定的点）

通过put（key，value）或者get（key），来存值或者查看值，还需要转换一步：通过位运算来得到index，从而插入到bucket中；

 

 

 HashMap和HashTable比较：

不同：

1.HashMap支持null值和null键的，而HashTable则会抛出空指针。原因是类内部做了处理。

2.HashMap不是线程安全的，而HashTable是线程安全的。因为HashTable中的方法的是用Synchronize同步过的

 如果HashMap想进行同步的话，可以用ConcurrentHashMap，采用了锁分段技术，不同的竞争资源采用不同的锁；

3.初始化的hashMap长度是16，而hashTable初始化长度是11；

 

相同：HashTable除了和HashMap有上述不同，其他基本相同，比如都用哈希表来Entry对象（含键值的对象）

 

fail-fast：指的就是多个线程在arraylist等非线程安全的集合中进行增删等操作时，造成的异常；