Hashtable哈希表的学习（数据结构）

                写下数据结构这四个字的时候很羞愧，大一的时候没有认真学习数据结构这门课，现在大三了，学习容器类时候遇到了它，好像听到它在和我说，以前陪人家看月亮的时候，叫人家小甜甜，现在新人胜旧人，就叫人家牛夫人？

                这个Hashtable不是Java里的那个容器类，而是一种数据结构！！！

             最近在看容器，发现Set和Map的结构和这个Hash词紧密相连·。存数据的时候需要重写hashCode和equals方法，hashCode一样时equals的值不一定为true，Object的hashCode的返回值是根据存储位置进行返回的，等等。所以我就学习了大佬们写的一些博客，从那里学习到了一些关于hash的知识，总结到自己的博客上，希望可以得到大佬的指正，自己也作为复习的一种方式。

                HashTable散列表是一种把数组（查询快）和链表（增删快）两者优势集中起来的一种数据结构。所以我们以下主要以数组和链表结合构成的散列表作为讨论对象，这种散列表可以理解成链表的数组，就是说每个数组的元素都是一个链表，至于为什么要这么做呢，一会再讲。

                

                为什么数组查询快呢？

               数组是一块连续的存储空间，空间的地址和数组下标一一对应，所以我们只要知道下标号，就可以直接找到存储地址，获取到值。而链表并不是连续的存储空间，单链表的元素只知道下一个元素的地址，所以如果链表要查找一个值，要一个个查找，费时费力。

                散列表利用数组的这个特点，把存入的数据和数组的下标关联起来，所以取数据的时候知道下标，取数据就很快了。

                为什么链表增删快呢？

                链表的删除过程，单链表中删除一个元素b只要把它的前一个元素a指向它的后一个元素c，

                a→b→c   变成  a→c 

                链表的增加过程，比如要把b加到a后面，把a本来指向c的指针，改成指向b的，再把b的指针指向c即可。

                a→c   变成  a→b→c 

                数组的删除和增加过程就非常感人了，不管是增还是删，都要把后面的数据进行移动操作，工作量比链表大很多。

                哈希表：一次存放key和value两项数据，根据key存取value数据，二者一一对应。java通过key这个关键字的特征（默认是根据地址）生成一个int型的特征值，使用的就是hashCode方法，得到的值叫做哈希值，可以自定义重写这个方法，写出的方法必须要确保同一个对象返回的hashCode相等，不然放进去的数据取不出来就尴尬了。然后根据生成的哈希值使用散列法，生成存储在哈希表里数组一个下标值，然后把数据添加到这个下标对应的链表上。

                所以取数据的时候就和数组一样非常快了，根据key得到他的哈希值，转换成数组下标，就可以从链表中取数据了。同样的，在链表中增删数据，你说够不够方便？

                这就是散列表优势的结合，查询的时候使用数组，增删用链表。

                HashCode的应用：

                1.加密算法：它把一些不同长度的信息转化成杂乱的128位编码，这些编码值叫做哈希值。MD5是目前应用最广泛的的生成HashCode的算法。

                2.查找：应用于哈希表，提供给我们了一种新的查找方式，以前的查找都是通过基于比较的查找算法进行查找，而哈希表却不需要。只要根据key即可得到hashCode，通过散列法在数组中对应的位置，直接可以定位到该位置获取到值，工作量大幅度减少。

                散列法：

                1.取模/除法散列法：

                        把hashCode对数组大小进行取模，得到的就是所在数组的位置下标。

                        所以我现在算是有点明白数组下标为啥要从0开始了！

                2.平方散列法：

                        由于取模操作是基于除法操作的，所以在运算效率上并不高，所以采用了一种对hashCode平方再移位运算方法。（因为HashMap的容量是以16为基数，进行2倍扩充，所以通过移位运算获得的值适用于HahsMap进行散列运算）

                3.斐波那契Fibonacci散列法

                        对平方散列法改进，试着去寻找一个数字，确保最后得到的值更加随机分布在数组的下标上，斐波那契数列（0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...）中找到了答案。

                        对于16位整数而言，这个乘数是40503 
                对于32位整数而言，这个乘数是2654435769 

                对于64位整数而言，这个乘数是11400714819323198485

               4.折叠法：
                这种方法是针对原始值为数字时使用，将原始值分为若干部分，然后将各部分叠加，得到的最后四个数字（或者取其他位数的数字都可以）来作为哈希值。
        5.基数转换法：
                当原始值是数字时，可以将原始值的数制基数转为一个不同的数字。例如，可以将十进制的原始值转为十六进制的哈希值。为了使哈希值的长度相同，可以省略高位数字。
        6.数据重排法：
                这种方法只是简单的将原始值中的数据打乱排序。比如可以将第三位到第六位的数字逆序排列，然后利用重排后的数字作为哈希值。

                

                散列冲突：下标总会有重复的时候，我们该怎么办呢？

                这就要说说为什么散列表上的每个元素的位置放的是一个链表了。有重复的就可以直接加到链表上去，取的时候根据key的hashCode去取value，当然hashCode也可能会有重复的适合，最后根据equals方法详细甄别。

                以上基于链表和数组的散列表，解决散列冲突的方法叫做拉链法Open hashing。(Java中应用拉链法)

                接下来讲的是基于数组的散列表是如何解决下标重复的散列冲突问题。

                开地址法Open addressing/Closed hashing:

                顾名思义，如果这个下标上有数据了，就再开一块新地址存储数据。

                1.线性探查法：从这个下标开始，向数组末端逐个查找，如果没找到空闲位置，再从头开始查找。

                缺点：容易造成连续的空间都是已经被使用的了，线性探查就会很费时间，这种现象称为聚集。

                2.二次探查法：是对线性探查法的改良，在当前下标基础上，进行加、减一个变量的平方和，这个变量从1开始递增，直到地址超出数组范围。

                缺点：二次探查法消除了聚集，但是如果存在较多的相同地址值的情况，会使这些值发生了二次聚集。

                3.双散列法：再使用一个散列函数产生固定的增量，进行地址变换。和线性探查法不同的是，线性探查是逐个查找，而双散列法是跳跃查找，减小了聚集的程度。

                这第二个散列函数生成值时也是有要求的

                        1.不能生成是0

                        2.生成的数不能是数组长度的因子（每检查一遍数组的时候，查的位置就都是一样了）

        注意：不可以简单的删除，因为删除后会影响之前对于地址的哈希冲突判断，所以一般会设置一个观察哨代表该位置被占用，当查找到这里时，直接跳过。

                4.建立缓冲区，把冲突的元素放入。

                总结一下散列表Hashtable这个数据结构

                优点：

                        1.兼顾了查找（几乎是常数时间O(1)完成）和增删的性能；

                        2.实现类key和value一一对应，改变了传统的查找方式，只需要知道key就能得到数据。

                缺点：

                        1.哈希冲突，是无法避免的，不同的元素可能得到相同的存储位置；

                      2.由于是基于数组的，扩充比较麻烦。当数据比较满的时候，哈希冲突几率大幅度增加，存取性能下降明显。（所以为了兼容数组的空间使用率和哈希冲突的概率，设置了一个叫做负载因子load factor的值，当数组存储的元素数量和数组容量的比值达到负载因子时，自动扩容。这个值默认是0.75，是一个经验值。）；

                        3.无法进行排序，内部存储是按hashCode返回的下标排序。所以要获取某一个范围内的多个数据，不易实现。