散列冲突

大家好，又见面了，我是你们的朋友全栈君。

概念：如果当一个元素被插入时与一个已经插入的元素散列到相同的值， 那么就会产生冲突， 这个冲突需要消除。解决这种冲突的方法有几种：本章介绍两种方法:分离链接法和开放定址法

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;
}
}