devbox
小舞很执着
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构第18节 散列表

作者：小舞很执着 | 2024-07-14 15:40:01

赞

踩

数据结构第18节 散列表

散列表（Hash Table），也称为哈希表，是一种数据结构，它使用哈希函数将键映射到数组的一个索引位置，从而可以快速地插入、查找和删除数据。散列表的核心在于哈希函数和解决冲突的策略。

在Java中，散列表的实现通常涉及以下几个关键部分：

  1. 哈希函数：用于将键转换为数组索引。
  2. 解决冲突：多个键可能映射到同一个数组索引，这称为冲突。常见的解决策略有链地址法（开放寻址法不在此讨论）。
  3. 负载因子：表示散列表的填充程度，当达到一定阈值时，散列表会自动扩容以减少冲突。

散列表实现示例

下面是一个简单的散列表实现，使用链表解决冲突：

import java.util.LinkedList;

public class SimpleHashTable<K, V> {
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    private LinkedList<Entry<K, V>>[] buckets;
    private int size;
    private float loadFactor;
    private int capacity;

    public SimpleHashTable(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    public SimpleHashTable(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0) {
            throw new IllegalArgumentException("Illegal capacity: " + initialCapacity);
        }
        if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
            throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
        }
        this.loadFactor = loadFactor;
        this.capacity = initialCapacity;
        this.buckets = new LinkedList[capacity];
    }

    public V put(K key, V value) {
        int hash = key.hashCode();
        int index = hash % capacity;
        LinkedList<Entry<K, V>> bucket = buckets[index];
        if (bucket == null) {
            bucket = new LinkedList<>();
            buckets[index] = bucket;
        }

        for (Entry<K, V> entry : bucket) {
            if (entry.getKey().equals(key)) {
                V oldValue = entry.getValue();
                entry.setValue(value);
                return oldValue;
            }
        }

        bucket.add(new Entry<>(key, value));
        size++;

        if ((float)size / capacity >= loadFactor) {
            resize();
        }

        return null;
    }

    public V get(K key) {
        int hash = key.hashCode();
        int index = hash % capacity;
        LinkedList<Entry<K, V>> bucket = buckets[index];
        if (bucket != null) {
            for (Entry<K, V> entry : bucket) {
                if (entry.getKey().equals(key)) {
                    return entry.getValue();
                }
            }
        }
        return null;
    }

    private void resize() {
        LinkedList<Entry<K, V>>[] oldBuckets = buckets;
        capacity *= 2;
        buckets = new LinkedList[capacity];

        for (LinkedList<Entry<K, V>> bucket : oldBuckets) {
            if (bucket != null) {
                for (Entry<K, V> entry : bucket) {
                    put(entry.getKey(), entry.getValue());
                }
            }
        }
    }

    private static class Entry<K, V> {
        private K key;
        private V value;

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        public void setValue(V value) {
            this.value = value;
        }
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102

使用示例

public class Main {
    public static void main(String[] args) {
        SimpleHashTable<String, Integer> table = new SimpleHashTable<>(16);
        table.put("one", 1);
        table.put("two", 2);
        table.put("three", 3);

        System.out.println(table.get("one"));  // 输出: 1
        System.out.println(table.get("two"));  // 输出: 2
        System.out.println(table.get("three"));  // 输出: 3
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

注意事项

  • 散列表的性能高度依赖于哈希函数的质量和冲突的解决策略。
  • 在实际应用中，散列表的大小通常是2的幂，以优化哈希函数的性能。
  • Java标准库中的HashMap类提供了更复杂和高效的散列表实现，包括更好的哈希函数和冲突解决策略。

以上示例展示了如何在Java中实现一个基本的散列表。在实际项目中，你可能会根据具体需求调整和优化这个实现，例如使用更高效的数据结构替代链表，或者实现更复杂的哈希函数。

为了进一步优化上述散列表的实现，我们可以做以下几点改进：

  1. 使用开放寻址法：开放寻址法（如线性探测、二次探测或双散列）可以在某些情况下比链地址法提供更好的性能，尤其是在高负载因子的情况下。
  2. 提高散列函数质量：使用更好的散列函数可以减少碰撞，提高散列表的效率。
  3. 使用更高效的数据结构：在解决冲突时，使用更高效的数据结构（如红黑树）代替链表，可以减少查找时间。
  4. 实现线程安全：如果散列表将在多线程环境中使用，确保其线程安全是非常重要的。
  5. 添加更多功能：如remove方法、containsKey、size等。

下面是一个采用线性探测开放寻址法的散列表实现，同时使用了更高效的散列函数：

import java.util.Arrays;

public class OptimizedHashTable<K, V> {
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    private Entry<K, V>[] table;
    private int size;
    private float loadFactor;
    private int capacity;

    public OptimizedHashTable(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    public OptimizedHashTable(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0) {
            throw new IllegalArgumentException("Illegal capacity: " + initialCapacity);
        }
        if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
            throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
        }
        this.loadFactor = loadFactor;
        this.capacity = initialCapacity;
        this.table = new Entry[capacity];
    }

    public V put(K key, V value) {
        int hash = key.hashCode();
        int index = hash & (capacity - 1); // 使用位运算优化
        int originalIndex = index;
        while (table[index] != null && !table[index].getKey().equals(key)) {
            index = (index + 1) & (capacity - 1); // 线性探测
            if (index == originalIndex) {
                throw new IllegalStateException("Table is full.");
            }
        }

        if (table[index] == null) {
            table[index] = new Entry<>(key, value);
            size++;
        } else {
            V oldValue = table[index].getValue();
            table[index].setValue(value);
            return oldValue;
        }

        if ((float)size / capacity >= loadFactor) {
            resize();
        }

        return null;
    }

    public V get(K key) {
        int hash = key.hashCode();
        int index = hash & (capacity - 1);
        int originalIndex = index;
        while (table[index] != null) {
            if (table[index].getKey().equals(key)) {
                return table[index].getValue();
            }
            index = (index + 1) & (capacity - 1);
            if (index == originalIndex) {
                break; // 防止无限循环
            }
        }
        return null;
    }

    private void resize() {
        Entry<K, V>[] oldTable = table;
        capacity *= 2;
        table = new Entry[capacity];
        size = 0;

        for (Entry<K, V> entry : oldTable) {
            if (entry != null) {
                put(entry.getKey(), entry.getValue());
            }
        }
    }

    private static class Entry<K, V> {
        private K key;
        private V value;

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        public void setValue(V value) {
            this.value = value;
        }
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103

在这个版本中，我们使用了线性探测来解决冲突，并且通过位运算优化了散列函数。请注意，开放寻址法可能导致散列表在接近满载时性能下降，因此需要谨慎选择负载因子和适当的重新散列策略。

此外，我们没有在上述代码中实现线程安全，因为这通常会增加复杂性和开销。在多线程环境下，可以考虑使用ConcurrentHashMap或其他线程安全的散列表实现。

为了进一步完善代码，我们可以添加一些实用的方法，比如remove方法来删除键值对，containsKey方法来检查是否存在某个键，以及size方法来返回散列表当前的元素数量。同时，为了保证线程安全，我们可以添加同步机制。以下是完善后的代码：

import java.util.Arrays;

public class OptimizedHashTable<K, V> {
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    private Entry<K, V>[] table;
    private int size;
    private float loadFactor;
    private int capacity;

    public OptimizedHashTable(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    public OptimizedHashTable(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0) {
            throw new IllegalArgumentException("Illegal capacity: " + initialCapacity);
        }
        if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
            throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
        }
        this.loadFactor = loadFactor;
        this.capacity = initialCapacity;
        this.table = new Entry[capacity];
    }

    public synchronized V put(K key, V value) {
        int hash = key.hashCode();
        int index = hash & (capacity - 1); 
        int originalIndex = index;
        while (table[index] != null && !table[index].getKey().equals(key)) {
            index = (index + 1) & (capacity - 1);
            if (index == originalIndex) {
                throw new IllegalStateException("Table is full.");
            }
        }

        if (table[index] == null) {
            table[index] = new Entry<>(key, value);
            size++;
        } else {
            V oldValue = table[index].getValue();
            table[index].setValue(value);
            return oldValue;
        }

        if ((float)size / capacity >= loadFactor) {
            resize();
        }

        return null;
    }

    public synchronized V get(K key) {
        int hash = key.hashCode();
        int index = hash & (capacity - 1);
        int originalIndex = index;
        while (table[index] != null) {
            if (table[index].getKey().equals(key)) {
                return table[index].getValue();
            }
            index = (index + 1) & (capacity - 1);
            if (index == originalIndex) {
                break;
            }
        }
        return null;
    }

    public synchronized V remove(K key) {
        int hash = key.hashCode();
        int index = hash & (capacity - 1);
        int originalIndex = index;
        while (table[index] != null) {
            if (table[index].getKey().equals(key)) {
                V removedValue = table[index].getValue();
                table[index] = null;
                size--;
                // Re-hash the remaining entries to avoid clustering
                rehashAfterRemove(index);
                return removedValue;
            }
            index = (index + 1) & (capacity - 1);
            if (index == originalIndex) {
                break;
            }
        }
        return null;
    }

    private synchronized void rehashAfterRemove(int removedIndex) {
        for (int i = (removedIndex + 1) & (capacity - 1); table[i] != null; i = (i + 1) & (capacity - 1)) {
            Entry<K, V> entry = table[i];
            table[i] = null;
            size--;
            put(entry.getKey(), entry.getValue());
        }
    }

    public synchronized boolean containsKey(K key) {
        int hash = key.hashCode();
        int index = hash & (capacity - 1);
        int originalIndex = index;
        while (table[index] != null) {
            if (table[index].getKey().equals(key)) {
                return true;
            }
            index = (index + 1) & (capacity - 1);
            if (index == originalIndex) {
                break;
            }
        }
        return false;
    }

    public synchronized int size() {
        return size;
    }

    private synchronized void resize() {
        Entry<K, V>[] oldTable = table;
        capacity *= 2;
        table = new Entry[capacity];
        size = 0;

        for (Entry<K, V> entry : oldTable) {
            if (entry != null) {
                put(entry.getKey(), entry.getValue());
            }
        }
    }

    private static class Entry<K, V> {
        private K key;
        private V value;

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        public void setValue(V value) {
            this.value = value;
        }
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153

在这个版本中，我们添加了remove、containsKey和size方法，并且所有修改散列表状态的方法都被声明为synchronized，以保证线程安全。但是，请注意，完全的线程安全可能会影响性能，因此在实际应用中，你可能需要根据具体场景权衡线程安全性和性能。

此外，rehashAfterRemove方法用于在删除元素后重新散列受影响的元素，以避免由于删除操作导致的散列表局部热点。这有助于维持散列表的良好性能。

让我们通过一个表格逐步展示上述优化后的散列表代码的运作流程。我们将使用一个初始容量为8，负载因子为0.75的散列表，并执行一系列的插入、查找、删除和扩容操作。

初始状态

IndexKeyValue
0
1
2
3
4
5
6
7

操作 1: 插入 (Key=1, Value=A)

IndexKeyValue
01A
1
2
3
4
5
6
7

操作 2: 插入 (Key=9, Value=B)

由于9 % 8 = 1，但Index 1是空的，所以直接插入。

IndexKeyValue
01A
19B
2
3
4
5
6
7

操作 3: 插入 (Key=17, Value=C)

由于17 % 8 = 1，但Index 1已被占用，进行线性探测，下一个位置2是空的，所以插入Index 2。

IndexKeyValue
01A
19B
217C
3
4
5
6
7

操作 4: 插入 (Key=25, Value=D)

由于25 % 8 = 1，并且Index 1和Index 2均被占用，继续线性探测，直到找到Index 3是空的，所以插入Index 3。

IndexKeyValue
01A
19B
217C
325D
4
5
6
7

操作 5: 查找 (Key=17)

从Index 1开始，线性探测直到找到Key=17位于Index 2。

IndexKeyValue
01A
19B
217C
325D
4
5
6
7

操作 6: 删除 (Key=9)

删除Key=9，并重新散列Index 2之后的所有元素。

IndexKeyValue
01A
1
217C
325D
4
5
6
7

操作 7: 插入 (Key=33, Value=E)

由于33 % 8 = 1，并且Index 1是空的，所以直接插入Index 1。

IndexKeyValue
01A
133E
217C
325D
4
5
6
7

操作 8: 插入 (Key=41, Value=F)

此时，size=5，达到扩容条件(size / capacity >= loadFactor)，因此先进行扩容操作，容量变为16，然后重新散列所有元素。

IndexKeyValue
01A
133E
217C
325D
………
1241F
………
15

通过上述步骤，我们可以清晰地看到散列表如何通过散列函数和线性探测来管理元素的插入、查找和删除操作，以及如何在达到特定条件时自动进行扩容，以保持良好的性能。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小舞很执着/article/detail/825352
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号