散列表（Hash表），HashMap，HashTable，Con

2018-09-27 本文已影响11人 Preupen

概念：Hash表是通过关键字用f()（hash函数）去找对应地址的数据结构；（就像查字典一样）
hash冲突：如果是多音字an（按，安）通过关键字查找的页数都是一样的,这样就形成了hash冲突也就是hash碰撞；
hash碰撞的常用解决方法有：1.开发定址法　2.链地址法
开放定址发：

图1

注意：上面所说的开发定址法的原理是遇到冲突的时候查找顺着原来哈希地址查找下一个空闲地址然后插入，但是也有一个问题就是如果空间不足，那他无法处理冲突也无法插入数据，因此需要装填因子(空间/插入数据)>=1。
链地址法（拉链法）：链地址法的原理时如果遇到冲突，他就会在原地址新建一个空间，然后以链表结点的形式插入到该空间。我感觉业界上用的最多的就是链地址法。（hashmap的解决方法）

图2
哈希表的性能：由于哈希表高效的特性，查找或者插入的情况在大多数情况下可以达到O(1)，时间主要花在计算hash上，当然也有最坏的情况就是hash值全都映射到同一个地址上，这样哈希表就会退化成链表，查找的时间复杂度变成O(n)，但是这种情况比较少，只要不要把hash计算的公式外漏出去并且有人故意攻击，一般也不会出现这种情况。

HashMap基于hash表原理，我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算最终的hashCode值，然后找到bucket位置来储存值对象。当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。

1.HashTable 上早期用来存储键值对的map，HashMap是在HashTable 之后出来的。
2.HashTable 线程安全因为HashTable 是同步的,HashMap不是同步的所以造成线程不安全。
3.hashmap的速度快于HashTable ，主要原因是遍历方式的内部实现上不同，HashMap中的迭代器是一个快速迭代器，而HashTable 用的枚举器。
4.HashMap的键和值可以是null，而HashTable不能

当你想多线程处理数据你就可以用ConCurrentHashMap，因为ConCurrentHashMap的处理速度快，HashTable是过时的散列表结构，缺陷有1.内部遍历处理速度慢，2.在多线程操作HashTable 时，HashTable 同步的是整个散列表，所以当一个线程操作put()方法时，另一个线程只能等该线程操作完成后才能操作HashTable ，而ConCurrentHashMap就不一样了，他实行分段锁，把整个散列表分成很多部分，当一个线程执行ConCurrentHashMap的put()时只是占用了这一部分的锁，此时其他线程能占用其他的get()去占用其他部分锁，所以他的效率要高于HashTable ，在多线程处理散列表时我们应该优先选择ConCurrentHashMap。