哈希表数据结构java,java哈希表遍历

　　00-1010哈希表概念通过折叠法、保余法、哈希冲突问题及其解决方法得出哈希函数的平均个数。开地址法、重哈希函数法、公共溢出区法、链地址法、填充哈希表因子码、实现哈希函数、添加数据、删除数据、判断哈希表是否为空、遍历哈希表得到哈希表存储的键值对个数。

　　00-1010哈希表又称散列表，利用哈希技术将记录存储在一个连续的存储空间中。在哈希表中，我们用一个函数f使存储位置=f(关键字)，这样就可以不用比较关键字就可以得到所需记录的存储位置。哈希技术的记录之间没有逻辑关系，只和关键字有关。因此，哈希主要是一种面向查找的存储结构。

　　00-1010施工原则：

　　简单哈希函数的计算时间不应超过其他搜索技术与关键词的比较时间。

　　哈希地址均匀分布解决冲突的最好办法就是让哈希地址尽可能均匀地分布在存储空间中。

　　确保存储空间的有效利用，减少处理冲突的时间。施工方法：

　　00-1010假设关键字是1234，那么它的平方就是1522756。提取中间的3位是227，用作哈希地址。比如关键词4321，那么它的平方就是18671041，中间三位数就是671或者710。去方块法更适用于关键字分布未知，位数不大的情况。

　　00-1010折叠法是将关键字从左到右分成若干个位数相等的部分(注意最后一部分位数不够时可以短一些)，然后将这些部分叠加求和，根据哈希表的长度，取若干位数作为哈希表的地址。

　　比如我们的关键字是9 8 7 6 5 4 3 2 1 0，哈希表的长度是3位。我们把它分成四组，9876543210，然后把它们加起来就是987 654 321 0=1962，然后计算最后3位得到962的哈希地址。

　　有时这不能保证均匀分布，所以从一端到另一端来回折叠，对齐添加。比如我们把987和321反过来，再加上654和0，就成了789 654 123 0=1566。此时，散列地址是566。

　　折叠法不需要事先知道关键词的分布，适用于关键词较多的情况。

　　00-1010这种方法是构造哈希函数最常用的方法。

　　公式是：

　　f(key)=key mod p (p=m)

　　代码如下：

　　public int hash func(int key){ return key % length；}

　　00-1010哈希冲突是指两个不同的关键字，但是哈希函数得到的地址是相同的。

　　Key1 key2，但f(key1)=f(key2)

　　同义词

　　此时，的key1和key2称为该哈希函数的同义词。

　　这是不可能的。一个单间怎么住两个人？

　　别担心，这个问题自然已经被有实力的大佬解决了。

　　00-1010开发寻址方法就是一旦有冲突就寻找下一个空哈希地址。只有哈希表足够大，总是可以找到空的哈希地址，并且记录存储在

　　示例：19 01 23 14 55 68 11 86 37存储在表长度为11的数组中，其中H(key)=key MOD 11

　　取决于填充因子，而不是取决于查找集合的键值对个数。Java中的HashMap默认初始容量为16，默认加载因子为0.75(当底层数组容量占用75%时，数组开始扩容,扩容后容量是原容量的二倍)，此时虽然浪费了一定空间，但是换来的是查找效率的大大提升。

代码实现

下面用链式地址法来实现哈希表。

public class HashTableDemo { //哈希表每个位置链表的节点 class Node{ //关键字 int key; String value; Node next; //无参构造 Node(){} //有参构造 Node(int key, String value){ this.key = key; this.value = value; next = null; } //重写哈希表的equals()方法 public boolean equals(Node node){ if(this == node) return true; else{ if(node == null) return false; else{ return this.value == node.value && this.key == node.key; } } } } //哈希表的长度 int length; //哈希表存的键值对个数 int size; //存储数据容器 Node table[]; //不指定初始化长度的无参构造 public HashTableDemo(){ length = 16; size = 0; table = new Node[length]; //为哈希表每一个位置初始化 for (int i = 0; i < length; i++) { table[i] = new Node(i,null); } } //指定初始化长度的有参构造 public HashTableDemo(int length){ this.length = length; size = 0; table = new Node[length]; for (int i = 0; i < length; i++) { table[i] = new Node(i,null); } }}

哈希函数

public int hashFunc(int key){ return key % length; }

添加数据

思路：

　　先通过哈希函数算出该键值对在table中的位置。遍历该处的链表的每一个节点，若发现某节点的key与传入的key相等，那么就更新此处的value。若未发现相等的key，那么在链表末尾添加新的节点.最后返回value。代码如下：

 public String put(int key, String value){ int index = hashFunc(key); //保证cur2始终是cur的前一个节点。 Node cur = table[index].next; Node cur2 = table[index]; while(cur != null){ if(cur.key == key){ cur.value = value; return value; } cur = cur.next; cur2 = cur2.next; } cur2.next = new Node(key, value); size++; return value; }

删除数据

思路：

　　先通过哈希函数算出该键值对在table中的位置。遍历该处的链表的每一个节点，若发现某节点的key与传入的key相等，那么就删除此节点，并返回它的value。若未发现相等的key，返回null。代码如下：

 public String remove(int key){ int index = hashFunc(key); Node cur = table[index]; while(cur.next != null){ if(cur.next.key == key){ size--; String value = cur.next.value; cur.next = cur.next.next; return value; } cur = cur.next; } return null; }

判断哈希表是否为空

思路：判断哈希表每个位置处的链表是否为空。

public boolean isEmpty(){ for(int i = 0; i < length; i++){ if(table[i].next != null) return false; } return true; }

遍历哈希表

 public void print(){ for(int i = 0; i < length; i++){ Node cur = table[i]; System.out.printf("第%d条链表: ",i); if(cur.next == null){ System.out.println("null"); continue; } cur = cur.next; while(cur != null){ System.out.print(cur.key + "---"+ cur.value + " "); cur = cur.next; } System.out.println(); } }

获得哈希表已存键值对个数

//返回哈希表已存数据个数 public int size(){ return size; }

到此这篇关于Java超详细分析讲解哈希表的文章就介绍到这了,更多相关Java哈希表内容请搜索盛行IT以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。