散列冲突
大家好，又见面了，我是你们的朋友全栈君。
概念：如果当一个元素被插入时与一个已经插入的元素散列到相同的值， 那么就会产生冲突， 这个冲突需要消除。解决这种冲突的方法有几种：本章介绍两种方法:分离链接法和开放定址法
1.分离链接法
其做法就是将散列到同一个值得所有元素保留到一个表中。我们可以使用标准库的实现方法。如果空间很紧(因为表是双向链表的并且浪费空间)。 为执行一次查找，我们使用散列函数来确定是那一个链表， 然后我们在被确定的链表中执行一次查找。
import java.util.LinkedList;
import java.util.List;
public class SeparateChainingHashTable<AnyType> {
private static final int DEFAULT_TABLE_SIZE = 101;
private List<AnyType>[] theLists;
private int currentSize;
public SeparateChainingHashTable(){
this(DEFAULT_TABLE_SIZE);
}
public SeparateChainingHashTable(int size){
theLists = new LinkedList[nextPrime(size)];
for(int i = 0; i < theLists.length; i++)
theLists[i] = new LinkedList<>();
}
public boolean contains(AnyType x){
List<AnyType> whichList = theLists[myhash(x)];
return whichList.contains(x);
}
/* * 数据的插入 */
public void insert(AnyType x){
List<AnyType> whichList = theLists[myhash(x)];
if(!whichList.contains(x)){
whichList.add(x);
//
if(++currentSize > theLists.length)
rehash();
}
}
/* * 数据的删除 */
public void remove(AnyType x){
List<AnyType> whichList = theLists[myhash(x)];
if(whichList.contains(x))
{
whichList.remove(x);
currentSize--;
}
}
public void makeEmpty(){
for(int i = 0; i < theLists.length; i++)
theLists[i].clear();
currentSize = 0;
}
private void allocateArray(){
for(int i = 0; i < theLists.length; i++)
theLists[i] = new LinkedList<>();
}
//将传过来的数变成质数
private static int nextPrime(int n){
if(n < 11)
return 11;
else if(isPrime(n))
return n;
else
while(true){
n++;
if(isPrime(n)){
return n;
}
}
}
//判断是不是质数
private static boolean isPrime(int n){
if(n % 2 != 0 && n % 3 != 0 && n % 5 != 0 && n % 7 != 0)
return true;
else
return false;
}
/* * 对分离链接散列表和探测散列表的在散列 */
private void rehash(){
List<AnyType> [] oldList = theLists;
theLists = new LinkedList[theLists.length * 2];
allocateArray();
for(int i = 0; i < oldList.length; i++){
List<AnyType> whichList = oldList[i];
for (AnyType x : whichList) {
insert(x);
}
}
}
/* * 散列表的myHash的方法 */
private int myhash(AnyType x){
int hashVal = x.hashCode();
hashVal %= theLists.length;
if(hashVal < 0)
hashVal += theLists.length;
return hashVal;
}
/*测试*/
public static void main(String[] args) {
SeparateChainingHashTable<String> hash = new SeparateChainingHashTable<>();
hash.insert("Tom");
hash.insert("SanZi");
System.out.println(hash.contains("Tom"));
}
}2.开放定址法
不用链表的散列表
2.1线性探测法
就是在插入冲突的时候， 当前位置有值存放的话， 那么就会到下一个位置存放。这种解决冲突的方法虽然在前期效果明显， 但是在插入数量比较庞大的时候。 它解决冲突的时间和链接法的时间相差无几。所以在线性探测这种情况下优化， （平方探测法）。
2.1平方探测法
public class QuadraicProbindHashTale<T> {
/** * 数据域 * @param <T> : 泛型，存放对象 */
private static class HashEntry<T>{
public T element;
public boolean isActive;
public HashEntry(T e){
this(e, true);
}
public HashEntry(T e, boolean i){
element = e;
isActive = i;
}
}
/* * 默认的大小为11 */
private static final int DEFAULT_TABLE_SIZE = 11;
private static int currentSize = 0;
private HashEntry<T>[] array;
public QuadraicProbindHashTale(){
this(DEFAULT_TABLE_SIZE);
}
/** * * @param size ： 表的大小 */
public QuadraicProbindHashTale(int size) {
allocateArray(size);//先判断传过来的size是不是质数， 如果不是， 把它变成质数， 这样方便hash计算和不容易出现冲突情况
makeEmpty();
}
/* * 判断对象是否在这个hash表当中 */
public boolean contains(T x){
int currentPos = findPos(x);
return isActive(currentPos);
}
/** * 数据的插入 * @param x ：数据的元素 * 首先调用findPox方法来判断在第一次执行hash的时候里面有没有元素，如果没有直接插入 * 如果有元素， 那么在存放的位置往后挪。（线性探测， 平方探测） */
public void insert(T x){
int currentPos = findPos(x);
if(isActive(currentPos))
return;
array[currentPos] = new HashEntry<>(x, true);
if(currentSize > array.length / 2)
rehash();
}
/** * 数据的删除 * @param x ：要删除的数据 * 在数据域内有识别这个内容是否有效的一个boolean类型， 当isActive是为true的时候， 表示有效 * 如果有效的话， 那么就删除。 */
public void remove(T x){
int currentPos = findPos(x);
if(isActive(currentPos))
array[currentPos].isActive = false;
}
/** */
private void rehash(){
HashEntry<T>[] oldArray = array;
allocateArray(nextPrime(2 * oldArray.length));
currentSize = 0;
for(int i = 0; i < oldArray.length; i++)
if(oldArray[i] != null && oldArray[i].isActive)
insert(oldArray[i].element);
}
private boolean isActive(int currentPos){
return array[currentPos] != null && array[currentPos].isActive;
}
/** * 查找在hash表中元素 * @param x ：要查找的元素 * @return 所在数组中的位置 */
private int findPos(T x){
int offset = 1;
int currentPos = myhash(x);
while(array[currentPos] != null && !array[currentPos].equals(x)){
currentPos += offset;
offset += 2;
if(currentPos >= array.length)
currentPos -= array.length;
}
return currentPos;
}
/* * 初始化hash表中的所有的值为空 */
public void makeEmpty(){
currentSize = 0;
for(int i = 0; i < array.length; i++)
array[i] = null;
}
private void allocateArray(int arraySize){
array = new HashEntry[nextPrime(arraySize)];
}
//将传过来的数变成质数
private static int nextPrime(int n){
if(n < 11)
return 11;
else if(isPrime(n))
return n;
else
while(true){
n++;
if(isPrime(n)){
return n;
}
}
}
//判断是不是质数
private static boolean isPrime(int n){
if(n % 2 != 0 && n % 3 != 0 && n % 5 != 0 && n % 7 != 0)
return true;
else
return false;
}
/* * 散列表的myHash的方法 */
private int myhash(T x){
int hashVal = x.hashCode();
hashVal %= array.length;
if(hashVal < 0)
hashVal += array.length;
return hashVal;
}
}发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/146361.html原文链接：https://javaforall.cn
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022年5月1，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
