java实现散列表

向右看齐 2022-07-12 16:26 224阅读 0赞

在直接寻址的情况下，具有关键字k的元素被存储在槽k中。比方说关键字域有2,3,5,8四个数，那么它只能被存储在2,3,5,8四个位置，其他的位置全部都被浪费掉了，这时候就可以通过散列函数h,将关键字域中的元素映射到散列表\[0,m-1\]的位置上。

这时候内存的花销就大大的减少了。

在JDK中已经有一个HashTable了，为了更加深刻的理解hash表，这里我们来自己实现一下:

散列函数定义为:

index=key%16;

通过链接法来解决碰撞问题:

下面是实现的

package bb;
    
    public class HashEntry {
    	public Integer key=null;
    	public Object value=0;
    	public HashEntry next=null;
    	public HashEntry pre=null;
    
    }

package bb;
    
    import java.util.ArrayList;
    
    public class MHashTable {
    	private int size=16;
    	private ArrayList<HashEntry> arrayList=new ArrayList<HashEntry>();
    	
    
    	public MHashTable() {
    		for(int i=0;i<size;i++){
    			arrayList.add(i,null);
    		}
    	}
    
    	public ArrayList<HashEntry> getContainer(){
    		return  arrayList;
    	}
    	public int getIndex(int key){
    		return key%16;
    	}
    	
    	public boolean insert(Integer key,int value){  
    	    if(get(key)!=null){  
    	        return false;  
    	    }  
    	    int theLocIndex=getIndex(key);  
    	    if(theLocIndex>=16){  
    	        return false;  
    	    }  
    	    if(arrayList.get(theLocIndex)==null){  
    	        HashEntry curEntry=new HashEntry();  
    	        curEntry.key=key;  
    	        curEntry.value=value;  
    	        arrayList.remove(theLocIndex);  
    	        arrayList.add(theLocIndex,curEntry);  
    	        return true;  
    	          
    	    }  
    	    else if(arrayList.get(theLocIndex)!=null){  
    	        HashEntry cEntry=arrayList.get(theLocIndex);  
    	        HashEntry preEntry1=cEntry;  
    	        while(cEntry!=null){  
    	            preEntry1=cEntry;  
    	            cEntry=cEntry.next;  
    	        }  
    	        HashEntry newEntry=new HashEntry();  
    	        newEntry.pre=cEntry;  
    	        newEntry.key=key;  
    	        newEntry.value=value;  
    	        preEntry1.next=newEntry;  
    	        return true;  
    	    }  
    	    return false;  
    	}  
    	  
    	public HashEntry get(Integer key){  
    	    int theLocIndex=getIndex(key);  
    	    if(arrayList.get(theLocIndex)==null){  
    	        return null;  
    	    }  
    	    else{  
    	        HashEntry cEntry=arrayList.get(theLocIndex);  
    	        while (cEntry!=null) {  
    	            if(cEntry.key==key){  
    	                return cEntry;  
    	            }  
    	            else{  
    	                cEntry=cEntry.next;  
    	            }  
    	              
    	        }  
    	        return null;  
    	          
    	    }  
    	}  
    	  
    	public boolean remove(int key){  
    	    int theLocIndex=getIndex(key);  
    	    if(arrayList.get(theLocIndex)==null){  
    	        return false;  
    	    }  
    	    else{  
    	        HashEntry cEntry=arrayList.get(theLocIndex);  
    	        while (cEntry!=null) {  
    	            if(cEntry.key==key){  
    	                if(cEntry.pre==null){  
    	                	arrayList.remove(theLocIndex);  
    	                    return true;  
    	                }else{  
    	                    cEntry.pre.next=cEntry.next;  
    	                    return true;  
    	                }  
    	            }  
    	            else{  
    	                cEntry=cEntry.next;  
    	            }  
    	              
    	        }  
    	        return false;  
    	          
    	    }     
    	}  
    	  
    	public boolean edit(int key,int value){  
    	    HashEntry cEntry=get(key);  
    	    if(cEntry==null){  
    	        return false;  
    	    }  
    	    cEntry.value=value;  
    	    return true;  
    	}  
    	/**
    	 * @param args
    	 */
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		MHashTable mHashTable=new MHashTable();
    		mHashTable.insert(1, 2);
    		mHashTable.insert(17, 3);
    		System.out.println(mHashTable.get(1));
    		System.out.println(mHashTable.get(17));
    	}
    
    }

做了一个简单的碰撞测试，最后是输出结果，显然这两个地址是不一样的

![Center][]

[Center]: /images/20220709/da700d6d5a98471abc6af7c7c02bc12c.png