hash表的实现原理
哈希表（Hash table，也叫散列表），所谓hash表，就是以 键-值(key-indexed) 的形式存储的数据结构。可以根据key来快速的查找到value。也就是说，它通过把key值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表
散列函数又叫hash（Hash函数），散列表也叫哈希表。
1.hash表怎么存储
hash表把key通过hash函数转化成一个特定的整数，然后与数组的长度取余，取余结果（hash值）当做该数组的下标，然后将value存储在意该下标中。 hash(key)%len。
根据上面的原理，首先，我们要分配一片空间用来存储我们数据，比如是一个空的数组
然后，有数据存进来的时候，按照特定规则得出这个数据在数组中的位置，将数据存进这个位置
我们就以存进一个整型数据为例，特定规则就是取余
根据计算出来的值，将这些数据放入对应的位置，我们的数组变为
然而，当查询hash表时，只要按照取余规则计算出这个数据在数组中对应的位置，然后查看数组的这个位置，就可以取出这个数据了，比如我们要从哈希表中取出52，根据取余规则，52的计算出来的位置是8，数组中8这个位置是空的，52不在哈希表中，找不到52的数据；从哈希表中取出77，77计算出来的位置是0，数组中0这个位置有值，而且值就是77，从哈希表中取出77的值。
2. 思考问题
- 如果根据取余计算出来的两个甚至多个hash值相同，该怎么存储。
- hash表满了，该怎么扩容。
3. 解决问题
1）解决hash冲突
对于第一个问题，就是我们常说的hash冲突。有开放定制法 和 拉链法。
拉链法
左边很明显是 数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。
从上图我们可以发现哈希表是由数组+链表组成的，一个长度为16的数组中，每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key)%len获得，也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中，12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。开放定制法
基本原理为，使用大小为M的数组来保存N个键值对，其中M>N，我们需要使用数组中的空位解决碰撞冲突
比如我们要存放88，哈希值是0，数组这个位置已经有值了，那我们再获取一个哈希值，比如在原哈希值的基础上加1，得到1，1的位置是空，我将88放进去。
插入88后的数组变为
冲突解决了，但我们读取数据的时候，好像又出现问题了，88的哈希值是0，发现数组0位置不是空的，那我们确定88在哈希表中？肯定不行，0这个位置存储的是77，不是88。我们的解决方法是判断0这个位置的值是不是88，不是的话，再计算88的哈希值是1，判断是1这个位置是否为空，为空，则88不在哈希表中；不为空，判断值是否为88，若是88，确定在哈希表中；如果值不是88，我们则继续计算哈希值是2，依次下去，直到找到88或者值为空的位置。
2）解决扩容
再分配一个大于原先空间的一片空间，把原来空间中的值重新哈希到新的空间中。
4.Hash的应用
1、Hash主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做Hash值. 也可以说，Hash就是找到一种数据内容和数据存放地址之间的映射关系。
2、查找：哈希表，又称为散列，是一种更加快捷的查找技术。我们之前的查找，都是这样一种思路：集合中拿出来一个元素，看看是否与我们要找的相等，如果不等，缩小范围，继续查找。而哈希表是完全另外一种思路：当我知道key值以后，我就可以直接计算出这个元素在集合中的位置，根本不需要一次又一次的查找！
举一个例子，假如我的数组A中，第i个元素里面装的key就是i，那么数字3肯定是在第3个位置，数字10肯定是在第10个位置。哈希表就是利用利用这种基本的思想，建立一个从key到位置的函数，然后进行直接计算查找。
3、Hash表在海量数据处理中有着广泛应用。