哈希表中的每个位置称为桶(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冲突 #### 一、引言 哈希表是一种非常高效的数据结构,通过哈希函数可以快速地定位到数据所在的存储位置。然而,在实际应用中,由于哈希函数的设计和数据分布的原因,经常会出现多个不同的...
在本例中,我们关注的是如何利用链地址法来处理哈希冲突。 哈希函数是哈希表的核心,它的作用是将任意长度的键转化为固定长度的哈希值,通常这个哈希值是数组的索引。在"哈希表 链地址法解决冲突"的场景中,哈希...
10. **Java集合框架中的`HashMap`**:虽然这里我们讨论的是自定义的链地址法实现,但Java标准库中的`HashMap`类也是采用链地址法处理哈希冲突的。`HashMap`提供了内置的高效哈希表实现,可以作为参考或与自定义实现...
链地址法是处理哈希冲突的一种方式,它利用数组的每一个元素不再仅存储一个值,而是存储一个链表。当新的关键码经过哈希函数映射到已有的位置时,就将其添加到该位置链表的末尾。这样,同一个哈希位置可以存放多个...
hash表一般都采用取余构造(将一个数对n取余然后根据余数来查找是否存在该数),当两个数的余数相同时仅仅凭借余数作为下标来查找就会发生错误即hash冲突,那么链地址法其实就是将余数相同的数用链表储存起来,那么...
查询操作在链接法处理冲突的散列表中同样高效。首先,我们计算查询键的散列值,然后查找对应索引处的链表。由于链表中的元素都是散列到同一位置的,因此在链表中进行线性搜索,直到找到目标键或者遍历完整个链表。 ...
链地址法处理这种冲突的方法是在每个哈希表的槽位处维护一个链表。所有映射到同一槽位的键都会链接在这个链表上。当查找、插入或删除元素时,我们只需要遍历对应槽位的链表即可。 3. **C语言实现**:C语言是面向...
本文将详细介绍一个基于C语言实现的哈希表查找系统,该系统利用链地址法处理冲突,并支持基本的增删查操作。通过本篇文章,您将了解哈希表的基本原理、链地址法的应用场景、以及具体的代码实现细节。 #### 二、哈希...
在“Hash-lookup.zip_hash冲突”这个主题中,我们主要探讨的是在使用哈希表进行查找时遇到的冲突问题以及解决策略。 哈希函数是哈希查找的核心,它的作用是将任意长度的关键字映射到固定大小的哈希表(也称为散列表...
5. **分离链接法(Robin Hood Hashing)**:在链地址法的基础上改进,当新元素哈希到已满的位置时,会比较其与当前位置元素的距离(即当前位置到理想位置的差距),如果新元素更接近理想位置,则替换当前位置的元素...
1. 开放地址法:这种方法是当发生冲突时,直接寻找下一个空的哈希地址。具体策略有线性探测再散列、二次探测再散列和双哈希法等。线性探测是简单地按顺序检查下一个槽位,直到找到空槽或完成整个表;二次探测则是...
在这个电话本管理系统中,很可能采用了链地址法来处理冲突,即每个数组元素不直接存储数据,而是存储一个链表,所有哈希值相同的键值对都存储在同一个链表中。当查找时,先计算键的哈希值,然后遍历对应链表找到对应...
总结来说,哈希冲突的解决方案主要涉及哈希函数的设计、冲突处理机制(如链地址法和开放寻址法)以及对哈希表大小的优化。在实际应用中,我们需要根据具体需求和性能指标来选择合适的方法。在字符串查找问题中,哈希...
哈希函数用除留余数法构造,用线性探测再散列法或链地址法处理冲突。 测试数据 取读者周围较熟悉的30个人名。 选作内容 (1) 从教科书上介绍的集中哈希函数构造方法中选出适用者并设计几个不同的哈希函数,比较...
这种方法结合了开放地址法和链地址法的特点,既可以利用空闲位置,又可以处理大量冲突。 选择哪种解决冲突的方法取决于具体的应用场景。例如,如果数据分布均匀,开放地址法可能是好的选择;如果冲突较多,链地址法...
3. **链地址法**:在每个哈希表的槽位上附加一个链表,所有映射到同一位置的键都存储在这个链表中。这种方法简单易实现,但链表过长会降低性能。 在实际应用中,哈希表的设计和优化至关重要。例如,选择合适的哈希...
6. **性能**:由于 UTHASH 使用了简单的哈希函数和链表法处理冲突,其性能可能会受到冲突率的影响。在设计结构体和选择哈希字段时,应尽量减少冲突,以优化查找和插入性能。 7. **源码可扩展性**:虽然 UTHASH 是一...