hash表简单实现
hash表简单实现
??? 1、什么是哈希表？
??? 哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
???2、如何实现实现哈希表
?? ?哈希表的做法其实很简单，就是把Key通过一个固定的算法函数即所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。当然，不同的数据可能会出现相同的下标，那么就把这些数据用链表“连”起来放入对应下标数组。
???? 当使用哈希表进行查询等操作的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间便利数组存放的链表获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位??
???3、简单实现
??? 因为只是为了实现一体现这种思想的哈希表，所以写了一个简单的hashForUI实现方法，以下是具体的代码：
?
?
?? 用户类：这里没有使用泛型，只是简单的希望哈希表能够存储用户类的数据，并且以用户的ID来作为索引，进行添加和查找
/** * 用户信息类 */public class UserInfo { private String userName;private int id;//构造函数public UserInfo(String userName,int id){this.userName = userName;this.id = id;} public String getUserName() {return userName;}public void setUserName(String userName) {this.userName = userName;}public int getId() {return id;}public void setId(int id) {this.id = id;}}?
?? 节点类：这是用来作为存放在数组中的链表结点，每个节点存放的数据类型是UserInfo，有一个后继指向下一个链表节点
/** * 结点类，作为存放在数组中的链表结点 * */public class Node {private UserInfo user;private Node next;//构造函数public Node(UserInfo user ,Node next){this.user = user;this.next = next;}public UserInfo getUser() {return user;}public void setUser(UserInfo user) {this.user = user;}public Node getNext() {return next;}public void setNext(Node next) {this.next = next;}}?
?? 这是具体的实现方法：
?? 这里关键码值使用的是UserInfo的ID,哈希函数也只是简单的
/** * 构建hashForUI表，实现insert，delete,rehash等方法 */public class hashForUI{private static int length = 10;//创建哈希表的数组，初始化长度是length;public static Node[] array = new Node[length]; private int count = 0;//表长private double loadFactor = 0.5;//装载因子//插入元素public void insert(UserInfo user){int index = calculate(user.getId());Node node = new Node(user,null);node.setNext(array[index]);array[index] = node;count ++;//判断是否需要rehashrehash();}}//删除元素public boolean delete(UserInfo user){int index = calculate(user.getId());if(array[index] == null){//数组为空return false; }else if(array[index].getUser().getId() == user.getId()){//第一个元素就是所找array[index] = array[index].getNext();}else{//第一个不是Node currentFirst = array[index];Node currentSecond = currentFirst.getNext();while(currentSecond != null){if(currentSecond.getUser().getId() == user.getId()){//第二个即所找currentFirst.setNext(currentSecond.getNext());count --;return true;}else{//后移currentFirst = currentSecond;currentSecond = currentSecond.getNext();}}}return false;}//查找元素public UserInfo find(int id){int index = calculate(id);//System.out.println(index+" "+id);for(Node current = array[index] ;current != null;current = current.getNext()){if(current.getUser().getId() == id){return current.getUser();}}return null;}//重新构建哈希表，每次增加数组长度100public void rehash(){//System.out.println((double)length/(double)count);if(((double)length/(double)count) < loadFactor){length = length*2;System.out.println(length);Node[] arrayCopy = new Node[length];//直接重新插入for(int i = 0;i < array.length;i++){Node node = array[i];while(node != null){//System.out.println("&&&");UserInfo user = node.getUser(); int index = calculate(user.getId());Node n = new Node(user,null);n.setNext(arrayCopy[index]);arrayCopy[index] = n;node = node.getNext();}}array = arrayCopy;}}//哈希表长public int length(){return count;}//哈希函数public int calculate(int x){return x%length;//return x.hashCode();}}?
/** * 测试类 */public class test {public static void main(String [] args){hashForUIh = new hashForUI();Long startTime1=System.currentTimeMillis();//记录开始时间for(int i = 0;i<650000;i++){UserInfo user = new UserInfo("User"+i,i);h.insert(user);}Long endTime1=System.currentTimeMillis();//记录结束时间System.out.println("hash插入元素所用时间"+(endTime1-startTime1));UserInfo user1 = new UserInfo("User"+1299,1299);boolean state = h.delete(user1);System.out.println(state);Long startTime2=System.currentTimeMillis();//记录开始时间user1 = h.find(1333);Long endTime2=System.currentTimeMillis();//记录结束时间System.out.println(user1.getUserName()+" "+user1.getId());System.out.println("hash查找元素所用时间"+(endTime2-startTime2));}}?运行结果：
hash插入元素所用时间1310
true
User1333??? 1333
hash查找元素所用时间0
?
如果输出每一次reHash后数组长度的改变，会发现当数据达到65W时，建立的数组大小是32W,也是相当巨大的………………
总之，只是简单实现了hash的思想，至于算法方面，有待提高~~~
?
?
?
?
?
?
?
?