哈希表中的每个位置称为桶(bucket),当发生哈希冲突时就以链表形式存放多个元素。
链地址法处理Hash冲突,看看下面代码,模拟了JDK中的HashSet:
class Node{//节点数据结构
private Object value;//节点的值
private Node next;//链表中指向下一结点的引用
/*提供了常见的操作*/
public Node(Object value){this.value = value;};
public Object getValue() {return value;}
public Node getNext() {return next;}
public void setNext(Node next){this.next=next;}
}
public class MyHashSet {//Hash数据结构
private Node[] array;//存储数据链表的数组
private int size = 0;//表示集合中存放的对象的数目
public MyHashSet(int length){
array = new Node[length];//创建数组
}
public int size(){
return size;
}
private static int hash (Object o){ //根据对象的哈希码得到一个优化的哈希码,
//算法参照java.util.HashMap的hash()方法
int h = o.hashCode();
h += ~(h<<9);
h ^= (h>>>14);
h += (h<<4);
h ^= (h>>>10);
return h;
}
private int indexFor(int hashCode){ //根据Hash码得到其索引位置
//算法参照java.util.HashMap的indexFor()方法
return hashCode & (array.length-1);
}
public void add(Object value) {//把对象加入集合,不允许加入重复的元素
int index = indexFor(hash(value));//先根据value得到index
System.out.println("index:" + index + " value:" + value);
Node newNode = new Node(value);//由value创建一个新节点newNode
Node node = array[index];//由index得到一个节点node
if (node == null) {//若这个由index得到的节点是空,则将新节点放入其中
array[index]=newNode;
size++;
} else {
//若不为空则遍历这个点上的链表(下一个节点要等于空或者该节点不等于新节点的值--不允许重复)
Node nextNode;
while (!node.getValue().equals(value) && (nextNode = node.getNext())!=null) {
node = nextNode;
}
if (!node.getValue().equals(value)) {
//若值不相等则加入新节点
node.setNext(newNode);
size++;
}
}
}
public boolean contains(Object value){
int index = indexFor(hash(value));
Node node = array[index];
while (node!=null && !node.getValue().equals(value)) {
node = node.getNext();
}//横向查找
if (node!=null && node.getValue().equals(value)) {
return true;
} else {
return false;
}
}
public boolean remove(Object value) {
int index = indexFor(hash(value));
Node node = array[index];
if (node!=null && node.getValue().equals(value)) {//若是第一个节点就是要remove的
array[index]=node.getNext();
size--;
return true;
}
Node lastNode = null;
while (node!=null && !node.getValue().equals(value)) {//若不是第一个节点就横向查找
lastNode = node;//记录上一个节点
node = node.getNext();
}
if (node!=null && node.getValue().equals(value)) {
lastNode.setNext(node.getNext());
size--;
return true;
}else {
return false;
}
}
public Object[] getAll() {
Object [] values = new Object[size];
int index = 0;
for (int i = 0; i < array.length; i++) {
Node node = array[i];
while (node!=null) {
values[index++]=node.getValue();
node = node.getNext();
}
}
return values;
}
public static void main(String[] args) {
MyHashSet set = new MyHashSet(6);
Object [] values = {"Tom","Mike","Mike","Jack","Mary","Linda","Rose","Jone"};
for (int i = 0; i < values.length; i++) {
set.add(values[i]);
}
set.remove("Mary");
System.out.println("size="+set.size());
values = set.getAll();
for (int i = 0; i < values.length; i++) {
System.out.println(values[i]);
}
System.out.println(set.contains("Jack"));
System.out.println(set.contains("Linda"));
System.out.println(set.contains("Jane"));
}
}
结果:
index:4 value:Tom
index:1 value:Mike
index:1 value:Mike
index:5 value:Jack
index:5 value:Mary
index:0 value:Linda
index:0 value:Rose
index:0 value:Jone
size=6
Linda
Rose
Jone
Mike
Tom
Jack
true
true
false
- 大小: 23.7 KB
分享到:
相关推荐
hash表一般都采用取余构造(将一个数对n取余然后根据余数来查找是否存在该数),当两个数的余数相同时仅仅凭借余数作为下标来查找就会发生错误即hash冲突,那么链地址法其实就是将余数相同的数用链表储存起来,那么...
哈希函数用除留余数法构造,用线性探测再散列法或链地址法处理冲突。 测试数据 取读者周围较熟悉的30个人名。 选作内容 (1) 从教科书上介绍的集中哈希函数构造方法中选出适用者并设计几个不同的哈希函数,比较...
表头插入,使用链地址法处理冲突的哈希查找算法
30个中国人姓名拼音,设计Hash表,平均查找长度不超过2,用除留余数法构造,用线性探测再散列,二次探测再散列和链地址法处理冲突。完成建表和查表操作。本人的课程设计作业
散列,散列函数采用除留余数法,解决冲突使用链接法,每个槽的链表为带头结点的双向链表。使用这种方法的关键是选择一个合适的除数m,可以选择m是与2的整数幂不太接近的质数
表中已有15,38,61,84四个元素,如果用线性探测法处理冲突,则元素49的存储地址是( )。 A. 8 B. 3 C. 5 D. 9 7. 平衡二叉树的查找效率呈( )数量级。 A. 常数阶 B. 线性阶 C. 对数阶 D. 平方阶 8. 设输入序列为...
//是采用链地址法,拉链法处理冲突的散列表结构 newname->next = nam[key2]->next; //利用用户名为关键字插入 nam[key2]->next=newname; return 0; } void create() //新建节点 { int i; phone=new pnode[20]...
(4)(3分)按以上数据, 用链地址法处理冲突(Hash函数H(key)=key % 13),画出示意图(不要写算法) 3.(3分)已知三棵树的森林如下,试把它转化为二叉树 A G N / \ / | \ / \ B C H I K O P / | \ / \ / | \...
5. 采用开放定址法处理散列表的冲突时,其平均查找长度( )。 A.低于链接法处理冲突 B. 高于链接法处理冲突 C.与链接法处理冲突相同 D.高于二分查找 6. 若需要利用形参直接访问实参时,应将形参变量说明为( )...
冲突处理 D. 散列函数和冲突处理 2. 顺序文件采用顺序结构实现文件的存储,对大型的顺序文件的少量修改,要求重新复制整个文件,代价很高,采用( )的方法可降低所需的代价。【北京邮电大学 2000 二、8 (20/8分...
9.45③ 假设哈希表长为m,哈希函数为H(x),用链地址法处理冲突。试编写输入一组关键字并建造哈希表的算法。 实现下列函数: int BuildHashTab(ChainHashTab &H, int n, HKeyType es[]) /* 直接调用下列函数 */ /*...
7.1 如何更好地处理图片法显示问题 7.2 如何显示图片直到页面加载完成 7.3 预加载显示图片的方法 7.4 Facebook风格的图片预加载 7.5 检查图片src是否有效 7.6 上下滑动的图片 7.7 淡入淡出一幅图片,进入另一幅图片 ...
3) 采用链地址的方法解决冲突; 4) 查找并显示给定电话号码的记录; 5、排序算法比较 任务 :利用随机函数产生10个样本(其中之一已为正序,之一为倒序),每个样本有20000随机整数,利用直接插入排序、希尔排序...
6.2.1. 用短语法声明选项 6.2.2. 用长语法声明选项 6.3. 读取(Fetching)选项和参数 6.3.1. 操作 Getopt 异常 6.3.2. 通过名字读取 (Fetching)选项 6.3.3. 报告选项 6.3.4. 读取非选项参数 6.4. 配置 Zend...