1、对比
数组(顺序表)：寻址容易
链表：插入与删除容易
哈希表：寻址容易，插入删除也容易的数据结构
2、哈希表的概念
哈希表（Hash table，也叫散列表）
是根据关键码值(Key value)而直接进行访问的数据结构，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。
关键码值(Key value)也可以当成是key的hash值， 这个映射函数叫做散列函数
存放记录的数组叫做散列表
3、哈希表的举例
定义一个数组：{14, 19, 5, 7, 21, 1, 13, 0, 18}
定义一个散列表：假设数组初始大小为13，所以定义一个大小为13 的数组 a[13];
定义一个散列函数: f(x) = x mod 13; ==> x为数组中的值，f(x) 求出数组的角标。
那么开始计算：
f(14) = 14 % 13 = 1，14存储在a[1]中；
f(19) = 19 % 13 = 6，19存储在a[6]中；
f(5) = 5 % 13 = 5，5存储在a[5]中；
f(7) = 7 % 13 = 7，7存储到a[7]中；
f(21) = 21 % 13 = 8，21存储到a[8]中；
f(1) = 1 % 13 = 1，1存储在a[1]中，此时发生了冲突（碰撞），因为a[1]中已经存储了数据，我们采用n+1的方式来解决碰撞问题，n + 1 = 2，所以将1存储在a[2]中；
f(13) = 13 % 13 = 0，13存储在a[0]中；
f(0) = 0 % 13 = 0，此时发生了冲突（碰撞），因为a[0]中已经存储了数据，我们采用n+1的方式来解决碰撞问题，由于a[1]、a[2]都存储了数据，直到找到a[3]，a[3]中没有数据，所以将0存储到a[3]中；
f(18) = 18 % 13 = 5，此时a[5]、a[6]、a[7]、a[8]都存储了值，角标5、6、7、8都会发生冲突（碰撞），所以将5存储到a[9]中；
最终的数组为：
角标 0 1 2 3 4 5 6 7 8 9 10 11 12
——————————————————————————————————————————————————————————————————
| 13 | 14 | 1 | 0 | | 5 | 19 | 7 | 21 | 18 | | | |
——————————————————————————————————————————————————————————————————
4、哈希表在Java中的体现
（1）HashTable
底层数组+链表实现，无论key还是value都不能为null，线程安全，实现线程安全的方式是在修改数据时锁住整个HashTable，效率低，ConcurrentHashMap做了相关优化
初始size为11，扩容：newsize = olesize*2+1
计算index的方法：index = (hash & 0x7FFFFFFF) % tab.length
（2）HashMap
底层数组+链表实现，可以存储null键和null值，线程不安全
初始size为16，扩容：newsize = oldsize*2，size一定为2的n次幂
扩容针对整个Map，每次扩容时，原来数组中的元素依次重新计算存放位置，并重新插入
插入元素后才判断该不该扩容，有可能无效扩容（插入后如果扩容，如果没有再次插入，就会产生无效扩容）
当Map中元素总数超过Entry数组的75%，触发扩容操作，为了减少链表长度，元素分配更均匀
计算index方法：index = hash & (tab.length – 1)
（3）ConcurrentHashMap
底层采用分段的数组+链表实现，线程安全
通过把整个Map分为N个Segment，可以提供相同的线程安全，但是效率提升N倍，默认提升16倍。(读操作不加锁，由于HashEntry的value变量是 volatile的，也能保证读取到最新的值。)
Hashtable的synchronized是针对整张Hash表的，即每次锁住整张表让线程独占，ConcurrentHashMap允许多个修改操作并发进行，其关键在于使用了锁分离技术
有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁
扩容：段内扩容（段内元素超过该段对应Entry数组长度的75%触发扩容，不会对整个Map进行扩容），插入前检测需不需要扩容，有效避免无效扩容
ConcurrentHashMap是使用了锁分段技术来保证线程安全的。
锁分段技术：首先将数据分成一段一段的存储，然后给每一段数据配一把锁，
当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。
ConcurrentHashMap提供了与Hashtable和SynchronizedMap不同的锁机制。Hashtable中采用的锁机制是一次锁住整个hash表，
从而在同一时刻只能由一个线程对其进行操作；而ConcurrentHashMap中则是一次锁住一个桶。
ConcurrentHashMap默认将hash表分为16个桶，诸如get、put、remove等常用操作只锁住当前需要用到的桶。
这样，原来只能一个线程进入，现在却能同时有16个写线程执行，并发性能的提升是显而易见的。
HashTable已被弃用；
如果要保证线程安全，则使用ConcurrentHashMap；
如果不需要保证线程安全，则使用HashMap；
HashMap的效率比ConcurrentHashMap高的多，实际上，需要考虑安全性的场景并不是很多，所以HashMap常被使用。
5、jdk 1.8前后区别
哈希表整体的设计采用拉链法。
jdk 1.8之前：哈希表 = 数组 + 链表
jdk 1.8开始：哈希表 = 数组 + 链表，当链表超过阈值，就会转换成红黑树，这时：哈希表 = 数组 + 链表 + 红黑树
[本章完...]
网友评论