首页 > 代码库 > 哈希表的构建与查询
哈希表的构建与查询
(本文内容来自互联网)
11.2 哈希函数构造方法
设要存放的数据元素有n个,存放数据元素的数组个数为m,哈希函数的设计目标,就是要使通过哈希函数得到的n个数据元素的哈希地址 。
1 除留余数法
除留余数法是用数据元素的关键字K除以哈希表长度m所得的余数作为哈希地址的方法。除留余数法的哈希函数h(K)为:
h(K) = K mod m
11.3 哈希冲突解决方法
解决哈希冲突的方法主要有开放定址法和链表法两大类。 开放定址法
开放定址法是一类以发生哈希冲突的哈希地址为自变量、通过某种哈希冲突函数得到一个新的空闲的哈希地址的方法。开放定址法的哈希冲突函数通常是一组。
1 线性探查法
线性探查法是从发生哈希冲突的地址d开始,依次探查d的下一个地址,直到找到一个空闲单元为止。线性探查法的数学递推描述公式为:
如下哈希表类的哈希函数采用除留余数法, 哈希冲突函数采用开放定址法中的线性探查法。
package cn.ls.hash; public class HashItem { int data=http://www.mamicode.com/0; >package cn.ls.hash; public class HashTable { private HashItem[] ht; // 哈希表数组 private int tableSize; // 哈希表的长度 private int currentSize; // 当前的表项个数 HashTable(int m) { // 构造函数 tableSize = m; ht = new HashItem[tableSize]; currentSize = 0; } public boolean isIn(int x) { // x是否已存在 int i = find(x); if (i >= 0) return true; else return false; } public int getValue(int i) { // 取数据元素值 return ht[i].data; } public int find(int x) { // 查找 int i = x % tableSize; int j = i; if (ht[j] == null) ht[j] = new HashItem(0);//设置info标记为0 //注意要加上非空判断. while (ht[j] != null && ht[j].info == 1 && ht[j].data != x) { // 说明存在冲突 j = (j + 1) % tableSize; // 得到下一个哈希地址 if (j == i) return -tableSize; // 若j == i表示已查找完了整个哈希表的数组,返回- tableSize } if (ht[j] != null && ht[j].info == 1) //此条件成立表示查找到 return j; // 返回该数据元素的下标 else //此时表示没有查找到 返回该数据元素哈希地址的负值 return -j; } public void insert(int x) throws Exception { // 插入 int i = find(x); // 查找x 是否已存在,并返回数组下标 if (i > 0) { // 如果x存在 throw new Exception("该数据已存在"); } else if (i != -tableSize) { // 如果x不存在 ht[-i] = new HashItem(x, 1); //插入数据元素x,并设置info标记为1 currentSize++; // 当前元素个数加1 } else { // 如果i等于-tableSize,表示哈希表已满 throw new Exception("哈希表已满无法插入"); } } public void delete(int x) throws Exception { // 删除 int i = find(x); // 查找x 是否已存在,并返回数组下标 if (i >= 0) { // 如果x存在 ht[i].info = 0; // 置为空闲状态 currentSize--; // 当前元素个数减1 } else { // 如果x不存在 throw new Exception("该数据不存在"); } } }package cn.ls.hash; public class Exam11_3 { public static void main(String[] args) { //7个数据元素,哈希表数组个数取11进行测试。 HashTable myHashTable = new HashTable(11); int[] a = { 180, 750, 600, 430, 541, 900, 460 }; int i, j, n = 7, item; try { for (i = 0; i < n; i++) myHashTable.insert(a[i]); for (i = 0; i < n; i++) { j = myHashTable.find(a[i]); if (j > 0) { item = myHashTable.getValue(j); System.out.println("j = " + j + " ht[] = " + item); } } if (myHashTable.isIn(430)) System.out.println("数据元素430在哈希表中"); else System.out.println("数据元素430不在哈希表中"); myHashTable.delete(430); if (myHashTable.isIn(430)) System.out.println("数据元素430在哈希表中"); else System.out.println("数据元素430不在哈希表中"); } catch (Exception e) { System.out.println(e.getMessage()); } } }
测试结果:j = 4 ht[] = 180
j = 2 ht[] = 750
j = 6 ht[] = 600
j = 1 ht[] = 430
j = 3 ht[] = 541
j = 9 ht[] = 900
j = 10 ht[] = 460
数据元素430在哈希表中
数据元素430不在哈希表中
哈希表的构建与查询
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。