今日，你hash了吗

今天，你hash了吗

今天，你hash了吗

Hash，如果对一个学英语的人来说，肯定翻译成“混杂，拼凑，搞糟，把…弄乱”。

最近的各种事务真的把我hash了，以至于没有认真研究hash，只好hash了一篇博客。

Hash表作为一种数据结构，事实上就是数组与链表的“混杂”，产生的原因也很简单：对于海量的数据，我们希望能够查找快捷，同时满足数据本身的增删方便。这两个优点分别在数组和链表中展现无遗，数组的下标有利于直接对应查找，而链表的指向性又方便了数据的动态改变。

为了中和二者优点，一种称为hash表的数据结构诞生了。

事实上哈希表有多种不同的实现方法，我解释的是最常用的一种方法——拉链法，我们可以理解为“链表的数组”，如图：

今日，你hash了吗

Hash表结合了数组与链表的优点体现在：

1、将数据根据数组长度进行分类。假设这个数组长度为16，用皮球来类比数据。就好比将所有皮球放到16个箱子里，任意一个皮球只能放在其中一个箱子，并且放在哪个箱子和皮球本身的特性有关。那么我们在寻找某个皮球时就只用在某个箱子里去找，因为这个箱子里的皮球都是这个特性，这样数据的检索量就大大缩减了，理想情况下缩减为1/16。

2、用链表解决hash冲突。事实上数据量一般会比数组长度大，这样很有可能多个数据对应同一个数组下标的空间，而数组本身不像箱子，它只能装一个数据，多出来的，就通过链表在后面动态增长。

当我们手动实现时，其实就是先写一个链表，再写把链表与数组相连。

一：一个简单的链表节点

public class ListNode {

	//数据
	Object data;
	//该类自身的引用，类似指针
    ListNode next;
    
    ListNode(Object o)
    {
        data=o;
        next=null;
    }
   
    Object getObject()
    {
        return data;
    }
    
    ListNode getnext()
    {
        return next;
    }
}

二：我把对链表的数据处理封装了起来

	//头
	private ListNode firstNode;
	//尾
    private ListNode lastNode;
  
	//增加新节点
    public void add(Object ob){
    	
    	if(firstNode!=null){
    		
    		ListNode newNode = new ListNode(ob);
    		lastNode.next = newNode;
    		lastNode = newNode;
    		
    	}else{
    		
    		ListNode newNode = new ListNode(ob);
    		firstNode = newNode;
    		lastNode = newNode;
    		
    	}
    	
    }
    
    //默认删除头结点
    public void delete(){
    	
    	if(firstNode!=null){
    		firstNode = firstNode.getnext();
    	}
    	
    }
    
    //插入到第k个节点
    public void insert(Object ob,int k){
    	
    	ListNode tem = firstNode;
    	for(int i=1;i<k;i++){
    		tem = tem.getnext();
    	}
    	if(tem!=null){
    		ListNode newNode = new ListNode(ob);
    		newNode.next = tem.getnext();
    		tem.next = newNode;
    		
    	}
    }
    
    //删除第k个节点
    public void cut(int k){
    	ListNode tem = firstNode;
    	for(int i=1;i<k;i++){
    		tem = tem.getnext();
    	}
    	if(tem!=null){
    		tem.next = tem.getnext().getnext();
    		
    	}
    }
    
    //顺序输出
    public void print(){
    	
    	ListNode tem = firstNode;
    	
    	while(tem!=null){
    		
    		System.out.print(tem.getObject()+"->");
    		tem = tem.getnext();
    		
    	}
    	
    }

三：hash表的实现，直接调用方法

//初始大小为100,初始值为null
	Node[] hash = new Node[100]; 
	
	//记录现有数据个数
		int n = 0;
	//装载因子，如果数据长度超过就自动增加
	double factor = 0.95;
	
	public void add(Object ob){
		
		//自增方法
		if(n>hash.length*factor){
			//重新分配空间给新的
			reHash();
		}
		
		int k = ob.hashCode()%hash.length;
		if(k<0){
			k = -k;
		}
	
		if(hash[k]==null){
			Node hashChild = new Node(); 
			hash[k] = hashChild;
			hash[k].add(ob);
			n++;
		}else{
			
			hash[k].add(ob);
		}
		
	}

四：rehash

黄金无足色，白璧有微瑕，任何一个数据结构都是有弱点的，不然也不会产生多种数据结构共存的繁荣景象。

当数据量不断增加时，可能链表长度已经非常长了，数组长度就相对比较小，直观上就像一个狭长的长方形。

（当然如果数组长度过长，数据量很少就进入另一个极端了：

这都是要避免的，毕竟最美的长方形是长宽符合黄金分割比的，什么形状大家懂得。）

所以，数组在数据量到达一定情况时要增长，这个过程叫做rehash

就是重新开一个更长的数组空间，将所有数据根据这个空间长度重新放进去，以追求一个完美的长方形。

public void reHash(){
		
		Node[] newHash = new Node[hash.length*2];
		int k;
		Object ob;
		Node tem;
		
		for(int i=0;i<n;i++){
		
			tem = hash[i];
			if(tem!=null){
				
				ListNode node = tem.getHead();
				
				while(node!=null){
					
					ob = node.getObject();
					k = ob.hashCode()%hash.length;
					if(k<0){
						k = -k;
					}
				
					if(newHash[k]==null){
						
						List hashChild = new List(); 
						newHash[k] = hashChild;
						newHash[k].add(ob);
						
					}else{
						newHash[k].add(ob);
					}
					node = node.getnext();
				}
				
			}
		}
		
		hash = newHash;
	}

hash的应用很广泛，我只是模仿了其中最最最基本的部分，还有更多的有待继续hash，不过今天就hash到此吧~

今日，你hash了吗

相关推荐