哈希（散列）的分离链接法 顶

代码语言：javascript复制

import java.util.Iterator;
import java.util.List;
import java.util.Random;
import java.util.LinkedList;

/**
 * Created by Administrator on 2018-02-21.
 */
public class SeparateChainingHashTable<AnyType> {
    private static final int DEFAULT_TABLE_SIZE = 10;
    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<>();
        }
    }
    private int myhash(AnyType x) {
        int hashVal = x.hashCode();
        hashVal %= theLists.length;
        if (hashVal < 0) {
            hashVal  = theLists.length;
        }
        return hashVal;
    }
    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 boolean contains(AnyType x) {
        List<AnyType> whichList = theLists[myhash(x)];
        return whichList.contains(x);
    }
    public void makeEmpty() {
        for (int i = 0;i < theLists.length;i  ) {
            theLists[i].clear();
        }
        currentSize = 0;
    }
    private void rehash() {
        List<AnyType>[] oldLists = theLists;
        theLists = new List[nextPrime(2 * theLists.length)];
        for(int j = 0;j < theLists.length;j  ){
            theLists[j] = new LinkedList<AnyType>();
        }
        currentSize = 0;
        for (int i = 0; i < oldLists.length; i  ) {
            for (AnyType item : oldLists[i]) {
                insert(item);
            }
        }
    }
    private static int nextPrime(int num) {
        if (num == 0 || num == 1 || num == 2) {
            return 2;
        }
        if (num % 2 == 0) {
            num  ;
        }
        while (!isPrime(num)) {
            num  = 2;
        }
        return num;
    }
    private static boolean isPrime(int num) {
        if (num == 2 || num == 3) {
            return true;
        }
        if (num == 1 || num % 2 == 0) {
            return false;
        }
        for (int i = 3; i * i <= num; i  = 2) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
    public void printTable() {
        for(int i = 0;i < theLists.length;i  ){
            System.out.println("-----");
            Iterator iterator = theLists[i].iterator();
            while(iterator.hasNext()){
                System.out.print(iterator.next()   " ");
            }
            System.out.println();
        }
    }
    public static void main(String[] args) {
        Random random = new Random();
        SeparateChainingHashTable<Integer> hashTable = new SeparateChainingHashTable<Integer>();
        for (int i = 0; i < 30; i  ) {
            hashTable.insert(random.nextInt(30));
        }
        hashTable.printTable();
    }
}

把散列到相同值的数放入到双向链表中保存。

链表

0 人点赞