对hash思想的理解以及hash表的实现

?????新的问题总是导致了新的理论和新技术的诞生，其中在计算机领域的有一件事情却不得不提出来让我们讨论一下，那边是java编程语言中的一种数据结构hash集合。java中hash集合最常用的有三种，分别是：hashSet,hashMap及其hashTable。

?

?

?

?一：哈希算法诞生的背景

?

????在十九世纪后半叶，计算机技术飞速发展，为了适应不断提高的高指标运行环境，计算机语言也是层出不穷，其中著名的有c/c++、java、jScript以及后来的c#等等。这些高级计算机语言成为了广大程序员手中的强有力的开发利器。然而在最早的时候，并没有出现像今天如此方便的计算机语言给我们自由发挥，但是随着信息时代的步步紧逼，新的问题就产生了。

???????由于信息量过大，使用传统的数据存储方法显然已经满足不了人们需求。因为那时在计算机中数据的存储结构的根本方法只有两种：数组和链表。这两种存储方法各有各自的优点和劣势。例如数组的优势在于数组的长度是固定的，它的每一个下标都指向着唯一的一个值，所以我们知道这样一来的话要在数组中找到一个元素就非常方便了，只需要知道该元素在数组的索引就行了。但是长度固定同时又成了他的缺点，当我们用一个数组来存储一些数据时，需要指定他的长度，但是我们又不知道我们的数据是否就可以被该数组全部装下，一旦超出了数组的长度就会出错。同时如果我们定义一个长度足够长的数组的话又没有必要，因为这样会占用很大一部分的内存，造成计算机的资源浪费。而且当我们要删除不必要的元素时，该索引位置的内存空间是不能被释放的。链表的优势的就在于存储数据时我们只需要将数据不断地接在节点上就行了，这也就意味着链表的长度的没有限制的，所以我们可以很方便的对链表中的数据进行插入，删除等操作。但是由于链表的每一个数据都是环环相扣的，所以当我们需要查询某一个元素时就不得不遍历所有的节点。这时效率就大打折扣了。

??????所以我们是否能够找到一个综合了数组和链表各自的优点的一种数据存储方式呢？答案就是哈希算法。哈希算法是由hash这个人发明的，哈希算法将任意长度的二进制值映射为固定长度的较小二进制值，这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母，随后的哈希都将产生不同的值。要找到散列为同一个值的两个不同的输入，在计算上是不可能的，所以数据的哈希值可以检验数据的完整性。

　　哈希表是根据设定的哈希函数H(key)和处理冲突方法将一组关键字映象到一个有限的地址区间上，并以关键字在地址区间中的象作为记录在表中的存储位置，这种表称为哈希表或散列，所得存储位置称为哈希地址或散列地址。作为线性数据结构与表格和队列等相比，哈希表无疑是查找速度比较快的一种。

?? 关于equals()方法和hashCode()方法的区别和联系大家可以花多点时间去关注一下。

???????? 二：哈希算法中的关键点

???说到hash算法的成功实现其实关键归功于hashCode的应用。当然这是我个人的理解。初学者可以这样理解，hashCode方法实际上返回的就是对象存储的物理地址（实际可能并不是）。??? 这样一来，当集合要添加新的元素时，先调用这个元素的hashCode方法，就一下子能定位到它应该放置的物理位置上。如果这个位置上没有元素，它就可以直接存储在这个位置上，不用再进行任何比较了；如果这个位置上已经有元素了，就调用它的equals方法与新元素进行比较，相同的话就不存了，不相同就散列其它的地址。所以这里存在一个冲突解决的问题。这样一来实际调用equals方法的次数就大大降低了，几乎只需要一两次。

?

????????三：实现hash表的基本思路

????由于hash表其实是一个数组+链表的结合体，所以要实现它必须结合数组和链表的知识构建。下面是本人对构建hash表的基本思路。

??? 1.我们需要指定一个具有初始容量的数组，这个数组的每一个元素实际上是一个链表。例如我们可以这样构建：

? ?

?
?
?其中的双向箭头表示里面的每一个链表都是双向链表，这样的话可以方便后面的操作。
?
?4.重建hashMap。这一步是很重要的一步，它是hash表的一个显著特点，因为关乎hash表的效率问题。这里首先要有一个控制量，这个控制量就是hashMap的加载因子。jdk类库里面使用的0.75f,当然这个可以随自己的需要而定。当这个hash表中的数据量超过了我们所设定的限度的时候，比如说我们设定为maxSize? = init_Capacity*0.75f,当size>maxSize时我们就reSetHash。
?
四： 下面是我自己的一个hashMap的实现代码
??? 
?
??
?其中一次的测试结果为：
??? ?1108????????????? 47
?? ??value999
?????null
? 这说明比jdk中的hashMap性能就差多了,我认为这主要是hash函数的设置不佳造成的，其次是Map.Entry<K,V>这个接口可能有优越的性能，我的代码中没有直接实现这个接口。
?