不使用链表的散列

2022-04-17
作者 songbirds
~8.27K 字

1. 5.4.1 线性探测法
2. 5.4.2 平方探测法
3. 5.4.3 双散列

《数据结构与算法分析Java语言描述》第五章5.4节读书笔记

分离链接法的缺点是使用了散列表，给这些新单元分配地址需要时间，导致算法速度有些减慢。另一种不使用链表的解决方法是尝试另外一些单元，直到找出单元为止。常见的是单元 $h_0(x),h_1(x),h_2(x),...$ 相继被试选，其中 $h_i(x) = (hash(x) + f(i)) \quad mod \quad TableSize$ ，且f(0) = 0。函数f是冲突解决方法。一般来说其装填因子 $\lambda = 0.5$ 。这样的表叫做探测散列表。

5.4.1 线性探测法

线性探测法中，冲突解决函数f是i的线性函数，典型的是f(i) = i (i >= 0, i++)。这相当于冲突时，从冲突的地址+i，i从0递增，直到找到一个空的位置插入。如下是对于一个长度为10的散列表插入[89, 18, 49, 58, 69]时的情况。解决冲突的函数是f(i) = i。

第一次冲突是在插入49时出现冲突(hash(x) = x)，根据冲突解决公式,h(49)=(hash(49) + 1) mod 10时。冲突解决，结束，49放入该位置。第二次是插入58时出现冲突，h(58) = (hash(58) + 3) mod 10时。冲突解决。由上可知，每次冲突出现时，只需要沿着冲突的位置继续向下寻找可用位置，直到解决冲突即可。只要表足够大，总可以找到一个空位置。但是可能花费较多的时间。另外，占据的单元会开始形成一些区块，其结果称为一次聚集。当出现冲突后，可能会需要多次试选才能解决冲突。
可以得到证明，（证明较为复杂）。使用线性探测，预期探测次数对于插入和不成功查找约为： $\frac{1}{2} (1 + \frac{1}{(1- \lambda)^2})$ ，而成功的查找来说则是 $\frac{1}{2} (1 + \frac{1}{1- \lambda})$ 。则插入与不成功查找的需要相同的次数，成功查找的次数比不成功查找的平均花费时间较少。
如果 $\lambda = 0.75$ ，则上述公式预计线性一次插入需8.5次探测，如过0.9，则需要50次探测。由此可以看到，如果表有超过一半被装填满的时候，线性探测法不是一个好的方法。

5.4.2 平方探测法

平方探测法是为了解决线性探测法的一次聚集问题。较为流行的选择 $f(i) = i^2$ ，这相当于冲突时，加 $i^2$ ，i从0开始递增，如下图，当49与89冲突时，放入0位置。下次58放入时，则按公式依次选择后，放入2位置。

对于平方探测法，一旦表的填充超过一半，则不够好。特别的，如果表的大小不是素数，在被填充一半之前，就不能一次找到空的单元了，证明如下。

定理5.1：如果使用平方探测法，且表的大小是素数，那么当表小于一半的时候，总能够插入一个元素。

证明：采用反证法

令表的大小TableSize是一个大于3的素数，证明前TableSize/2个备选位置是互异的。 $h(x) + i^2(mod \quad TableSize)$ 和 $h(x) + j^2(mod \quad TableSize)$ 是这些位置的其中两个，其中0 <= , j <= TableSize/2 (注意会向下取整，且tableSize是素数)。为推出矛盾，我们假设前两个位置相同，但 $i \ne j$ ，于是有

h(x) + i^2 = h(x) + j ^2 \qquad (mod \quad TableSize)

i^2 = j^2 \qquad \qquad \qquad \qquad (mod \quad TableSize)

(i-j) + (i + j) = 0 \qquad (mod \quad TableSize)

由于TableSize是素数，要么i - j = 0，要么i+j=0。由于i，j互异，则第一个选择不可能，又因为0 <= i，j <= tableSIze/2，则第二个选择不可能。从而，前tableSize/2个备选位置都是互异的。则推出如上定理5.1。

即使表的填充位置只比一半多一个，则也可能插入失败。同时删除操作不能执行，因为相应的单元可能已经引起冲突，元素绕过它存在了别处，那么所有剩下的contains操作都会失败，因此探测表散列需要惰性删除，
探测表散列的大部分实现如下，此处不使用链表数组，使用单元数组HashEntry，其每一项有下列三种情形：

null
非null，且该项是活动的（isActive 为true）
非null，且该项已被标记删除（isActive 为false）

平方探测法的实现（展开）

ps: 判断是否时素数isPrime()方法，平方探测findPos()具体后移动平方的实现方法，这两个方法经典。

public class QuadraticProbingHashTable<AnyType> {

    private static final int DEFAULT_TABLE_SIZE = 11;
    private HashEntry<AnyType>[] array;
    private int currentSize;

    public QuadraticProbingHashTable() {
        // 调用另一个构造方法，需要传参数的那个构造方法。
        this(DEFAULT_TABLE_SIZE);
    }

    public QuadraticProbingHashTable(int size) {
        allocateArray(size);
        makeEmpty();
    }

    public void makeEmpty() {
        currentSize = 0;
        // 将所有元素置null
        Arrays.fill(array, null);
    }

    /**
     * 初始化HashEntry数组
     * @param arraySize 给定的HashEntry数组的大小，会自动调整为素数
     */
    private void allocateArray(int arraySize) {
        this.array = new HashEntry[nextPrime(arraySize)];
    }

    public boolean contains(AnyType x) {
        int currentPos = findPos(x);
        return isActive(currentPos);
    }

    public int size() {
        return currentSize;
    }

    public int capacity() {
        return array.length;
    }

    /**
     * 插入元素
     * @param x 插入的元素x
     * @return 是否插入成功
     */
    public boolean insert(AnyType x) {
        // findPos会按平方探测法找到一个没有被占用的位置
        int currentPos = findPos(x);
        if (isActive(currentPos)) {
            return false;
        }
        // 插入（数组）
        array[currentPos] = new HashEntry<>(x, true);
        currentSize++;
        // 平方探测法超过一半需要扩容并rehash
        if (currentPos > array.length / 2) {
            rehash();
        }
        return true;
    }

    /**
     * 删除元素
     * @param x 被删除的元素x
     * @return 是否删除成功
     */
    public boolean remove(AnyType x) {
        // 查找到元素的位置
        int currentPos = findPos(x);
        if (isActive(currentPos)) {
            // 标记为被删除
            array[currentPos].isActive = false;
            currentSize--;
            return true;
        } else {
            return false;
        }
    }

    /**
     * 扩容并拷贝到新数组，注意此处惰性删除的元素会被真正的删除
     */
    private void rehash() {
        HashEntry<AnyType>[] oldArray = array;
        allocateArray(2 * oldArray.length);
        currentSize = 0;
        for (HashEntry<AnyType> entry : oldArray) {
            if (entry != null && entry.isActive) {
                insert(entry.element);
            }
        }
    }

    /**
     * 查询元素的节点位置
     * @param x 元素x
     * @return 元素所在位置的下标
     */
    private int findPos(AnyType x) {
        int offset = 1;
        // 通过hash计算出节点的位置
        int currentPos = myHash(x);
        // 如果节点不为空且不相等，则需要继续往后找
        while (array[currentPos] != null && !array[currentPos].element.equals(x)) {
            // 这里实现了平方探测查找，首先currentPos + 1, currentPos + 1 + 3; currentPos + 1 + 3 + 5...
            currentPos += offset;
            offset += 2;
            // 实现环行查找
            if (currentPos >= array.length) {
                currentPos -= array.length;
            }
        }

        return currentPos;
    }

    /**
     * 节点是否激活
     * @param currentPos 节点位置
     * @return 如果节点被激活（没有被惰性删除）返回true, 否则返回false
     */
    private boolean isActive(int currentPos) {
        return array[currentPos] != null && array[currentPos].isActive;
    }

    private int myHash(AnyType x) {
        int hashVal = x.hashCode();
        hashVal %= array.length;
        if (hashVal < 0) {
            hashVal += array.length;
        }
        return hashVal;
    }

    /**
     * 根据传说的数获取素数
     * @param arraySize 素数的大小
     * @return 新的素数
     */
    private static int nextPrime(int arraySize) {
        if (arraySize % 2 == 0) {
            arraySize++;
        }
        while (!isPrime(arraySize)) {
            arraySize += 2;
        }

        return arraySize;
    }

    /**
     * 判断一个正整数是否是素数
     * @param n  数n
     * @return 素数：true;
     */
    private static boolean isPrime( int n ) {
        if( n == 2 || n == 3 ) {
            return true;
        }
        if( n == 1 || n % 2 == 0 ) {
            return false;
        }
        for( int i = 3; i * i <= n; i += 2 ) {
            if( n % i == 0 ) {
                return false;
            }
        }
        return true;
    }

    /**
     * HashEntry内部内，用来存储HashTable的元素
     * @param <AnyType>
     */
    private static class HashEntry<AnyType> {
        public AnyType element;
        /**
         * 如果被惰性删除则为false
         */
        public boolean isActive;

        public HashEntry(AnyType element) {
            this.element = element;
        }

        public HashEntry(AnyType element, boolean isActive) {
            this.element = element;
            this.isActive = isActive;
        }
    }
}

平方探测法解决了一次聚集，但是散列(计算到插入同一位置)到同一位置时，将继续往后探索相同的备选单元。这称为二次聚集。下面的双散列将解决这个问题，代价是要计算一个附加的散列函数。

5.4.3 双散列

双散列简单来说就是采取两个散列函数，其中一个散列计算具体的落入的位置，第二个散列是在冲突后，要从冲突的位置移动的步长。例如 $hash_1(x) = x \ \ mod \ \ tableSize$ （tableSize必须为素数）， $hash_2(x) = R - (x \ mod \ R)$ ，（R必须为素数）。

这里取tableSize = 10（计算方便），R = 7（小于tableSize 的素数）。首先89存入，下标9的位置没有冲突，直接存入，不计算散列函数2。假设再49插入时计算散列函数1，发现插入位置9发生冲突，需要计算散列函数2， $hash_2(49) = 7 - (49 \ \% \ 7) = 7$ 。从9开始，移动7个步长，所以移动到6的位置。

Songbirds

不使用链表的散列

5.4.1 线性探测法

5.4.2 平方探测法

5.4.3 双散列

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可

Songbirds

5.4.1 线性探测法

5.4.2 平方探测法

5.4.3 双散列

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可