挂链式Hash表的实现

?

?????? 最基本的数据结构是数组和链表，这两种数据结构各有优缺点，比如数组，查找容易，插入困难；而链表插入容易，查找困难。在作画图板的重绘时用的是自定义队列保存图形的形状，在自定义队列中是包装了对数组的各种操作，当时没注意到这种自定义队列的优缺点。今天以保存自己作的简单的IM系统的用户的账号为例，实现一个自己所理解的Hash表，以充分利用以上两种基本数据结构的优点。

??????? 首先要理解Hash表的相关概念：在相关教材上是这样定义的：根据设定的哈希函数和处理冲突的方法将一组关键字映像到一个有限的连续的地址集上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表称为哈希表，这一映像过程称为哈希造表或散列。在构造哈希表的过程中最重要的是哈希函数的选择，此类函数要为均匀的哈希函数，也就是要具有一致性，再一个就是哈希冲突的解决，所谓的哈希的冲突就是经过哈希函数计算得到相同是下标值，最后一个就是reHash，也就是当表中数据的存储达到一定的程度时要重新经过哈希函数的计算存到更大的表中。哈希函数的构造方法有直接定址法、数字分析法、平方取中法、折叠法、除留余数法等，在这里我选择的是JDK的HashMap中优化好的哈希函数；而哈希冲突的解决有开放定址法、再哈希法、链地址法、建立一个公共溢出区等，在这里用的是链地址法，也就是经过哈希函数计算出数据的在数组中的存储位置、如果有相同的存储位置则构建链表将新加入的元素加到链表的末尾，简单的说就是数组中的元素存的是链表。话已经说到这里了，先上代码，代码中的注释比较清楚，就不多解释了，如有不正确的地方欢迎各位指出纠正。

下面是一个UserInfo类的代码

?测试的代码：
?
public static void main(String args[]){MyHash ms = new MyHash();for (int i=1001;i<1100;i++){UserInfo user = new UserInfo();user.setJkNum(i);LinkNode tempNode = new LinkNode();tempNode.setUser(user);tempNode.setNode(null);ms.setNode(ms.node, tempNode);//ms.putData(user);}System.out.println("----------------");//UserInfo user = new UserInfo();//user.setJkNum(1001);ms.getData(9999);}
?
?