【算法】散列表及散列函数的java简单实现

发布时间:2016-12-10 18:52:26 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"【算法】散列表及散列函数的java简单实现",主要涉及到【算法】散列表及散列函数的java简单实现方面的内容,对于【算法】散列表及散列函数的java简单实现感兴趣的同学可以参考一下。

【前言】 想必大家对散列表及散列函数有所了解了。 当然,散列表有两个重点问题:1、如何将一个数字映射到数组下标; 2、如何处理冲突问题?   ok,鉴于这是演示简单的哈希表,散列函数这样定义: index=key%16; 而冲突的处理如何: 当映射到的位置一样,就将相关数据压入同一位置的链表。   【补充】遗憾的是没有在大数据下面测算效率。   核心代码如下:   package MyHashTable; public class hashEntry { public Integer key=null; public int value=0; public hashEntry next=null; public hashEntry pre=null; }     package MyHashTable; import java.util.ArrayList; import java.util.HashMap; /** * 这是一个自制的哈希表,里面的散列函数采用的是: * 斐波那契(Fibonacci)散列法 平方散列法的缺点是显而易见的,所以我们能不能找出一个理想的乘数,而不是拿value本身当作乘数呢?答案是肯定的。 1,对于16位整数而言,这个乘数是40503 2,对于32位整数而言,这个乘数是2654435769 3,对于64位整数而言,这个乘数是11400714819323198485 ==》例如:对于一个容量为16的哈希表,那么公式为: 对我们常见的32位整数而言,公式: index = (value * 2654435769) >> (32-4) 4为log2 16. 请哈希表的容量请使用2n次方根。 这里还有一个问题没有解决,就是假如key是字符串,那么如何映射? 还有就是哈希表的扩容问题。 * */ public class myhashtable { private int size=16; private ArrayList<hashEntry> _container=new ArrayList<hashEntry>(size); public myhashtable(){ for(int i=0;i<size;i++){ _container.add(i, null); } } public ArrayList<hashEntry> getContainer(){ return _container; } private int getIndex(int key){ //return (key * 40503) >>(32-4); 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(_container.get(theLocIndex)==null){ hashEntry curEntry=new hashEntry(); curEntry.key=key; curEntry.value=value; _container.remove(theLocIndex); _container.add(theLocIndex,curEntry); return true; } else if(_container.get(theLocIndex)!=null){ hashEntry cEntry=_container.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(_container.get(theLocIndex)==null){ return null; } else{ hashEntry cEntry=_container.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(_container.get(theLocIndex)==null){ return false; } else{ hashEntry cEntry=_container.get(theLocIndex); while (cEntry!=null) { if(cEntry.key==key){ if(cEntry.pre==null){ _container.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; } }     ok,下面放出演示的程序: 【插入键值对:12-17】 【插入键值对:28-19】   【插入键值对:45-3】   【插入键值对:78-41】   【插入键值对:2-147】   【插入键值对:44-7】   删除及编辑扥都是类似的,但是哈希表不应该是这么简陋。假如大家对这个演示程序有兴趣,那么可以到下面下载:    swing版简易哈希表演示工具

上一篇:基于ubuntu10.04的tftp开发环境搭建
下一篇:Android及Robotium学习总结【环境变量,真机调试及根据id模拟按键】

相关文章

相关评论