Hash表实现的意义
作为数据类型的一种,Hash表做到了数组和链表两类基本数据类型的完美结合。Hash表继承两者的优点,让我们在做数据处理方面有了很多的方便,不但是时间上的还有空间上的。在数组中我们知道,存放的数据与及记录的关键字上没有太多的关系,很多都只是一个随机的关系。那么这样在我们进行相应的操作时,会大大的减少我们的工作效率,主要是因为找数据时会进行一系列的比较,这样消耗的比较的次数太多时花费的时间就会变多,自然而然效率就这样被削弱了。所以最最理想的情况就是我们能直接通过他们建立的关系,直接的找到结构中的位置来获取数据。
关系怎么建立呢
现在我们的主要任务就是找到方法来建立对应的关系。这里的方法其实有很多种。不同的数据采用的方法不同。主要有数据分析法、平均取中法、取余法、随机数等等方法。在这里不做具体的介绍。所以今天我在自定义自己的Hash表时,用的是JDK中提供的hashCode()方法。有兴趣的还可以相应的拓展。
Hash表到底是什么
真的是真的,听了我说上面的你也许还没有理解Hash表是个什么东东。一句话:就是以链表为元素的数组对象。在我们将数据放在这个所谓的数组对象时,有两种情况:1:原来数组在该下标已经有元素存在了,那么要放入的节点如果经过hashCode()及indexFor()方法计算过后他的下标也是一样的,那么我们采用挂链法将这个节点放到最后;2:如果没有,那么放到对应的index下标中,作为根节点。
最清楚的Hash表代码解释
说了这些肯定也不会马上理解,没事,我们来看代码。
为了大家能够看的清楚明了,这里我建立三个类:一个是链表类、一个是Hash表、一个是测试类
里面的方法都有详细的介绍,主要的是把思路理清。
链表Entry类:
package 哈希表1029; /** * 链表 * @author 祝侦科 * */ public class Entry<K,V> { Entry<K,V> next; K key; V value; int hash; public Entry(K key,V value,int hash){ this.key = key; this.value = value; this.hash = hash; } }
哈希表类:
package 哈希表1029; /** * 自定义的哈希表 * @author 祝侦科 * */ public class Hash<K,V> { private int size;//链表数组的大小 private static int INIT_CAPACITY = 16;//默认的容量,即数组的大小 private static float LOAD_FACTOR = 0.75f;//默认的装载因子 private int max;//能存的最大的数 private Entry<K,V>[] entryArray;//链表数组 public Hash(int capacity,float factor){ this.INIT_CAPACITY = capacity; max = (int)(capacity*factor); entryArray = new Entry[capacity]; } public Hash(){ this(INIT_CAPACITY, LOAD_FACTOR); } /** * 根据hashcode及数组的容量来计算出该哈希码的下标 * @param hashcode hash值 * @param arraySize 数组长度 * @return 下标 */ public int indexFor(int hashcode,int arraySize){ return hashcode & (arraySize-1); } /** * 扩容以减少冲突阀值 * @param arraySize:扩容后新数组的容量 */ public void reHash(int arraySize){ //创建扩容后的数组 Entry<K,V>[] newArray = new Entry[arraySize]; max = (int)(arraySize*LOAD_FACTOR); for(int i=0;i<entryArray.length;i++){ //取得每一个链表对象 Entry<K,V> entry = entryArray[i]; while( null != entry){//遍历链表的每个节点,并且将节点加到新的数组中 this.setEntry(entry, newArray); entry = entry.next; } } entryArray = newArray;//将新的数组赋给原来的数组 } /** * 将节点放到链表数组中 * @param temp:要放入的节点 * @param entryArray:放到这个数组中 * @return:没有完全相同的则返回true,否则false */ public boolean setEntry(Entry<K,V> temp,Entry[] entryArray){ int index = this.indexFor(temp.hashCode(), entryArray.length);//获取要放入的节点的下标 Entry<K,V> entry = entryArray[index];//得到对应的链表对象 if(entry != null){//在while循环中遍历这个链表 while(null != entry){//遍历整个链表是为了发现是否有相同的节点 if((temp.key == entry.key || temp.key.equals(entry.key)) &&(temp.value == entry.value || temp.value.equals(entry.value)) && temp.hash == entry.hash){ return false;//这里要注意比较的方法。。要两种情况都比较 } //只有key相同时,value不同时 else if(temp.key == entry.key && temp.value != entry.value){ entry.value = temp.value; return true; } //当key不同时,则比较下一个元素 else if(temp.key != entry.key){ if(null == entry.next){ break; } entry = entry.next; } } //如果没有发现相同的话,则挂在最后面 this.addLastEntry(entry, temp); return true; } //当entry为null时,将元素放在最开始 this.addFirstEntry(temp, entryArray, index); return true; } /** * 将数据存到Hash表中 * @param k * @param v * @return */ public boolean put(K k,V v){ int hash = k.hashCode();//首先计算出hash值 Entry<K,V> entry = new Entry(k,v,hash); //将entry加到数组中 if(setEntry(entry, entryArray)){ size++; return true; } return false; } public V get (K k){ //先得到下标 int hash = k.hashCode(); int index = this.indexFor(hash, entryArray.length); //得到链表 Entry<K,V> entry = entryArray[index]; if(entry == null){ return null; } //遍历整个链表。。比较k值是否相等。。相等则返回对应的value while(null == entry){ if(entry.key == k || entry.key.equals(k)){ return entry.value; } entry = entry.next; } //不等的话则返回null return null; } /** * 要放的节点要放在某个数组元素(未有元素)中时,将节点设为根节点 * @param temp:要放入的链表 * @param entryArray:链表放入的数组 * @param index:链表在数组中的下标 */ public void addFirstEntry(Entry<K,V> temp,Entry[] entryArray,int index){ if(size > max){//如果容量超标,则扩容 this.reHash(entryArray.length*2); } entryArray[index] = temp;//将链表放在指定的下标中 temp.next = null;//temp是根节点,后面什么都没有了 } /** * 挂链法:将加点挂到相应节点的后面 ***** !!!!!第二个节点参数在后面的!!!!!****(这个顺序要注意!!) * @param entry:要挂在这个节点的后面 * @param temp:要挂的节点 */ public void addLastEntry(Entry<K,V> entry,Entry<K,V> temp){ if(size >max){ reHash(entryArray.length); } entry.next = temp;//挂在后面 } }
最后是测试类:
package 哈希表1029; public class HashTest { /** * @param args */ public static void main(String[] args) { new HashTest().test(args); } public void test(String[] args){ Hash<String ,String> hash = new Hash<String,String>(); long beginPut = System.currentTimeMillis(); for(int i=0;i<1000000;i++){ hash.put("", ""+i); } long endPut = System.currentTimeMillis(); System.out.println("存放数据用时:"+(endPut-beginPut)); long beginGet = System.currentTimeMillis(); hash.get(""+10000); long endGet = System.currentTimeMillis(); System.out.println("获取数据用时:"+(endGet-beginGet)); } }
随后最后运行的结果是:
希望我的讲解能给大家的Hash表的学习带帮助,也希望大家能够多多给我提建议,大家共同进步!
附件:
Hash表源代码包
相关推荐
自己整理的数据结构哈希表详解,参考其他博客、算法导论。包括哈希表构造方法、解决冲突的方法、包含牛客上的练习题。
NULL 博文链接:https://839127406.iteye.com/blog/1966131
哈希表 以上代码实现了一个简单的哈希表。在代码中,通过定义struct Node结构表示哈希节点,包含...在示例中,演示了插入键值对、打印哈希表、查找键对应的值、删除键值对等操作。你可以根据自己的需求进行扩展和修改。
c语言基础 c语言基础_c语言编程基础之哈希表编程示例
哈希表的建立和查找哈希表的建立和查找哈希表的建立和查找哈希表的建立和查找
对一批关键字集合采用开放定址哈希表的存储结构来建立相应的哈希表和完成查找过程。 (1) 熟练掌握哈希表的构造方法 (2) 理解哈希表与其他结构表的实质性差别。
哈希表
/为班级30个人的姓名设计一个哈希表,假设姓名用汉语拼音表示。要求用除留余数法 构造哈希函数,用线性探测再散列法处理冲突,平均查找长度的上限为2。 编写数据结构和算法来实现。要求:将哈希函数和处理冲突方法...
哈希表应用 设计哈希表实现图书查找系统,完成相应的建表和查表程序。从键盘输入各图书相关信息,分别以图书编号为关键字建立散列表。待填入哈希表的书号至少30个;构造合适的哈希函数。 (1)记录由外部输入。 (2...
哈希表设计程序设计+数据结构实验报告 1.1 针对某个集体中的人名设计一个哈希表,使得平均查找长度不超过R,完成相应的建立和查表程序. 1.2 人名为汉语拼音形式,最长不超过18个字符(如:庄双双 zhuangshuangshuang)...
////采用除留余数法定义哈希表,哈希表长度为10,哈希函数为H(key)=key%13。产生冲突时采用线性探测法实现下面要求的功能。 ////(1)初始化哈希表,置空哈希表 ////(2)在哈希表中查找元素 ////(3)在哈希表中...
哈希表课程设计数据结构实验报告——哈希表设计 针对某个集体中的人名设计一个哈希表,使得平均查找长度不超过R,完成相应的建立和查表程序. 1.2 人名为汉语拼音形式,最长不超过18个字符(如:庄双双 ...
鱼刺线程池例程 哈希表 标签反馈 多线程示例。模块:。哈希表asm 哈希表类_汇编版(HashMap_ASM) 支持自定义数据值。@skychat。
哈希表的概念作用及意义,哈希表的构造方法
哈希表的设计与实现课程设计 问题描述:针对某个单位电话号码簿,设计一个哈希表,并完成相应的建表和查表程序。 基本要求:设每个记录有下列数据项:电话号码、用户名、住址。从键盘输入各记录,以用户名为关键字...
哈希表的设计与实现——链地址法 问题描述: 设计哈希表实现电话号码查找系统。 基本要求: (1)设每个记录有下列数据项:电话号码、用户名、地址; (2)从文件中读取各记录,分别以电话号码和用户名为关键字建立...
问题描述:针对某个单位电话号码簿,设计一个哈希表,并完成相应的建表和查表程序。 基本要求:设每个记录有下列数据项:电话号码、用户名、住址。从键盘输入各记录,以用户名为关键字建立哈希表,哈希函数用除留取...
用C语言实现的哈希表设计,内有姓名列表,只要输入姓名就可得到查到在哈希表中的相应位置
简单哈希表模型。可以助你更好的完成哈希表相关的编程。
假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的上限为2。哈希函数用除留余数法构造,用线性探测再散列法或链地址法处理冲突。