Hash表

前面讲解了顺序表和链表，两者的优点和缺点都非常明显。

  顺序表特点：寻址容易，插入删除困难
  链表特点 ：寻址困难，插入删除容易

  那么，我们肯定会想，有没有这样一种数据结构，它能融合以上两种线性表的优点即：寻址也容易，插入删除也快呢？答案是肯定的，这就是我们今天要分析的hash表。

  hash表定义：哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

上面的定义来源于百度百科，定义往往说的不是人话，但我们可以从定义中抓取到几个重要的关键词。
  1.关键码值
  2.散列函数
  3.数组
  4.散列表

  首先，hash表存储的数据结构是一个数组，其次存储数据的形式是以key-value的形式来存储的，第三数据存储的位置是由指定的散列函数来决定的，最终才形成了一个散列表。

  那么，通过以上信息，我们可以得到一个什么信息呢？首先数据是存在数组中的，既然是数组，那么我们首先得知道他的大小。其次，既然是数组，那么它的扩容必定是麻烦的，这个我们后面再讲。

  通过以上概念，我们简单来走一遍hash表的存储过程。

  首先，我们得有一个散列函数。简单一点f(x)= x mod 10
  其次，我们既然要存储数据，我们得有一个数组。array[10]
  最后，我们定义一下我们要存储的数据。前面说到，hash表存储的数据是key-value这种形式的。那么，我们就定义8对这样的数据吧。

  由于本人不喜欢用电脑画图，并且感觉效率比较低，一般我都用笔纸画。

  先看一下我们的准备工作。

  一开始，我们的散列表是空的，默认将它的length设为10。

1524976644231.jpg

  现在，我们根据散列函数即f(x)=x mod 10 找到对应数据存储的位置。

1524976850844.jpg

  当我们在找<12,6>这对数据的时候，我们发现，a2这个位置已经存储过数据了。这就有冲突了。那么，我们要如何来解决这个冲突呢？ 冲突的解决方式我们可以自己定义。
  比如说，当产生冲突时，我们往数组的后一位继续查找，如果不存在数据，那么我们就往里存，如果存在的话就继续往下找，直到找到空的位置为止。查找的方式也要遵循如上原则，先通过散列函数查找到对应的索引位置，确认索引位置的key与我们要查找的key相同，才将数据返回；若不相同，则按照解决冲突的函数往下找，直到找到对应的key，才将对应的value返回。

最终，我们的数据存入hash表中的结果就是这样的。

1524977120157.jpg

当然，常见的hash表的存储肯定不是我们这样的简单，我们只是通过这样的方式能够让大家更容易理解。而事实上，常见的hash表其实是通过这样一种方式来存储的。

hash表.jpg

  看到这张图，大家是不是很熟悉？
  先看左边，是不是就是一个数组。右边呢，就是我们之前分析过的单链表。
  这就是为什么我们说hash表融合了顺序表和链表的优点。他的寻址是通过散列函数找到对应的数组的索引，他的数据的插入删除又是以链表的形式。所以说hash表寻址也快，数据的插入删除也快。

  那么，hash表就没有缺点了吗？

  首先，hash表的底层首先是一个数组，那么数组的缺点也是一个hash表的缺点，扩容的时候效率低，所以我们在使用hash表的时候最好是能够确定他的大小。
  其次，当hash表的散列函数使用不当时，很容易造成冲突，那么当一个hash表存在有大量的冲突数据的时候，那么他的性能就会大打折扣。

  在java中，常见的hash表有HashMap和HashTable。那么，这两者之间有什么区别呢？这是在面试过程中我们常被问到的一个问题。

HashMap和HashTable的区别表现在以下几个方面：
  1.HashMap几乎可以等价于HashTable，除了HashMap是非synchronized的，并可以接受null(HashMap可以接受为null的键值(key)和值(value)，而HashTable则不行)。
  2.HashMap是非synchronized，而HashTable是synchronized，这意味着HashTable是线程安全的，多个线程可以共享一个HashTable；而如果没有正确的同步的话，多个线程是不能共享HashMap的。Java 5提供了ConcurrentHashMap，它是HashTable的替代，比HashTable的扩展性更好。
  3.另一个区别是HashMap的迭代器(Iterator)是fail-fast迭代器，而HashTable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构（增加或者移除元素），将会抛出ConcurrentModificationException，但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为，要看JVM。这条同样也是Enumeration和Iterator的区别。
  4.由于HashTable是线程安全的也是synchronized，所以在单线程环境下它比HashMap要慢。如果你不需要同步，只需要单一线程，那么使用HashMap性能要好过HashTable。
  5.HashMap不能保证随着时间的推移Map中的元素次序是不变的。

有兴趣的同学可以去研究一下二者的源码，来验证一下上面的准确性。