数据结构第一弹-哈希表

🕗 发布于 2024-12-10 20:56 散列表 数据结构 哈希算法

大家好，今天和大家一起分享一下数据结构中的哈希表~

哈希表（Hash Table）是一种非常重要的数据结构，它通过使用哈希函数将键（key）映射到一个固定范围的索引值上，从而实现快速的查找、插入和删除操作。哈希表在许多领域都有广泛的应用，包括数据库管理、缓存系统、编译器设计等。

1. 哈希表概述

哈希表的主要目的是提供一种快速访问数据的方法。理想情况下，哈希表可以在常数时间O(1)内完成查找、插入和删除操作。然而，在实际应用中，由于碰撞（即不同的键可能被映射到相同的索引位置）的存在，性能可能会有所下降。为了处理碰撞，通常采用链地址法或开放地址法等策略。

1.1 基本概念

哈希函数：用于将任意大小的输入转换为固定大小输出的函数。理想的哈希函数应当具有良好的分布性，使得不同输入尽可能均匀地分布在哈希表的所有槽位上。
负载因子：哈希表中已存储元素数量与总槽位数的比例。当负载因子过高时，哈希表的性能会显著下降，因此需要适时进行扩容。
碰撞：当两个不同的键经过哈希函数计算后得到相同的索引时发生的现象。解决碰撞是哈希表设计中的关键挑战之一。

2. 哈希函数的设计

选择合适的哈希函数对于哈希表的表现至关重要。一个好的哈希函数应该满足以下条件：

简单性：易于计算。
均匀性：尽量减少碰撞发生的概率。
确定性：相同输入总是产生相同的输出。

常见的哈希函数构造方法包括直接定址法、除留余数法、折叠法等。其中，除留余数法是最常用的一种，其基本思想是取键值除以哈希表长度后的余数作为索引。

int hash(int key, int tableSize) {
    return key % tableSize;
}

3. 碰撞处理策略

3.1 链地址法

链地址法是处理碰撞的一种常用方式。每个哈希表槽位都指向一个链表头节点，所有哈希值相同的元素都会被链接在这个链表中。这种方法的优点在于可以轻松应对大量碰撞，但缺点是在极端情况下可能导致某些槽位的链表过长，影响查询效率。

Java代码示例 - 链地址法哈希表

public class HashTable<K, V> {

    private static final int INITIAL_CAPACITY = 16;
    private Entry<K, V>[] table;
    private int size;

    public HashTable() {
        this(INITIAL_CAPACITY);
    }

    @SuppressWarnings("unchecked")
    public HashTable(int capacity) {
        table = new Entry[capacity];
        size = 0;
    }

    private int hash(K key) {
        return (key.hashCode() & 0x7fffffff) % table.length;
    }

    public void put(K key, V value) {
        if (key == null) throw new IllegalArgumentException("Key cannot be null");
        int index = hash(key);
        for (Entry<K, V> entry = table[index]; entry != null; entry = entry.next) {
            if (entry.key.equals(key)) {
                entry.value = value;
                return;
            }
        }

        table[index] = new Entry<>(key, value, table[index]);
        if (++size > table.length * 2 / 3) resize();
    }

    public V get(K key) {
        if (key == null) return null;

        int index = hash(key);
        for (Entry<K, V> entry = table[index]; entry != null; entry = entry.next) {
            if (entry.key.equals(key)) {
                return entry.value;
            }
        }
        return null;
    }

    private void resize() {
        Entry<K, V>[] oldTable = table;
        int newCapacity = oldTable.length * 2;

        @SuppressWarnings("unchecked")
        Entry<K, V>[] newTable = new Entry[newCapacity];
        table = newTable;

        for (Entry<K, V> entry : oldTable) {
            while (entry != null) {
                Entry<K, V> next = entry.next;
                int newIndex = (entry.key.hashCode() & 0x7fffffff) % newCapacity;
                entry.next = newTable[newIndex];
                newTable[newIndex] = entry;
                entry = next;
            }
        }
    }

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

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

3.2 开放地址法

开放地址法尝试找到下一个可用的空槽位来存放冲突项。常见的探测序列包括线性探测、二次探测和双重散列等。这种方法能够避免额外的空间开销，但在高负载因子下容易形成聚集现象，导致性能恶化。

Java代码示例 - 开放地址法哈希表

public class OpenAddressingHashTable<K, V> {

    private static final int INITIAL_CAPACITY = 16;
    private Entry<K, V>[] table;
    private int size;

    public OpenAddressingHashTable() {
       this(INITIAL_CAPACITY);
    }

    @SuppressWarnings("unchecked")
    public OpenAddressingHashTable(int capacity) {
        table = new Entry[capacity];
        size = 0;
    }

    private int hash(K key) {
        return (key.hashCode() & 0x7fffffff) % table.length;
    }

    private int rehash(int h) {
        // Simple linear probing
        return (h + 1) % table.length;
    }

    public void put(K key, V value) {
        if (key == null) throw new IllegalArgumentException("Key cannot be null");
        if (size >= table.length * 3 / 4) resize();
        int index = hash(key);
        for (int i = 0; ; i++) {
            int newIndex = (index + i) % table.length;
            if (table[newIndex] == null || table[newIndex].status == Status.DELETED) {
                table[newIndex] = new Entry<>(key, value, Status.ACTIVE);
                size++;
                break;
            } else if (table[newIndex].key.equals(key)) {
                table[newIndex].value = value;
                break;
            }
        }
    }

    public V get(K key) {
        if (key == null) return null;
        int index = hash(key);
        for (int i = 0; ; i++) {
            int newIndex = (index + i) % table.length;
            if (table[newIndex] == null) return null;
            if (table[newIndex].status == Status.ACTIVE && table[newIndex].key.equals(key)) {
                return table[newIndex].value;
            }
        }
    }

    private void resize() {
        int newCapacity = table.length * 2;
        @SuppressWarnings("unchecked")
        Entry<K, V>[] newTable = new Entry[newCapacity];
        for (Entry<K, V> entry : table) {
            if (entry != null && entry.status == Status.ACTIVE) {
                int newIndex = (entry.key.hashCode() & 0x7fffffff) % newCapacity;
                for (int i = 0; ; i++) {
                    int probeIndex = (newIndex + i) % newCapacity;
                    if (newTable[probeIndex] == null) {
                        newTable[probeIndex] = new Entry<>(entry.key, entry.value, Status.ACTIVE);
                        break;
                    }
                }
            }
        }
        table = newTable;
    }

    private enum Status { ACTIVE, DELETED }

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

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

4. 性能分析

理论上，哈希表可以在平均情况下达到O(1)的时间复杂度。然而，实际性能取决于哈希函数的质量以及处理碰撞的方式。在最坏的情况下，例如所有的键都被映射到了同一个槽位上，哈希表的性能可能会退化到O(n)。因此，合理选择哈希函数并有效管理负载因子是保证哈希表高效运行的关键。

5. 应用实例

5.1 缓存系统

在网络服务中，缓存经常用来存储频繁访问的数据，以减轻数据库的压力。哈希表非常适合这种场景，因为它提供了快速的数据检索能力。

5.2 字典实现

字典或映射是一种常见的数据类型，允许用户通过键来访问值。哈希表是实现字典的理想选择，因为它支持高效的查找、插入和删除操作。

5.3 数据库索引

数据库管理系统利用哈希表来加速特定类型的查询。例如，哈希索引可以迅速定位到具有特定键值记录的位置，从而提高读取速度。

哈希表以其卓越的性能成为了现代软件开发中不可或缺的一部分。通过合理设计哈希函数和碰撞解决策略，我们可以构建出既高效又可靠的哈希表。无论是用于简单的键值对存储还是复杂的分布式系统中，哈希表都是一个强大的工具，欢迎大家一起评论区讨论~

原文地址：https://blog.csdn.net/fengxiaotao_cool/article/details/144300899

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Clip使用
下一篇：Helm安装Mysql8主从复制集群

.NET(C#) 如何配置用户首选项及保存用户设置
.NET(C#) 如何配置用户首选项及保存用户设置
阅读更多2024-12-14
【最新】北大数字普惠金融指数数据集-省市县（2011-2023年）
郭峰,王靖一,王芳,孔涛,张勋,程志云.测度中国数字普惠金融发展:指数编制与空间特征[J].经济学(季刊),2020,19(04):1401-1418.时间跨度：省级和城市级指数时间跨度为2011-2
阅读更多2024-12-14
GESP202412 四级【Recamán】题解（AC）
a11ak−1−kkakak−1−kak−1k小杨想知道 Recamán 数列的前n项从小到大排序后的结果。手动计算非常困难，小杨希望你能帮他解决这个问题。
阅读更多2024-12-14
IDEA遇到EasyConnect中的网络资源无法访问的问题
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。原文链接：https://blog.csdn.net/wanshanyu_/article/de
阅读更多2024-12-14
双目摄像头标定方法
此时已经完成标定，左下角为反投影误差，右边为外参可视化。将双目左右目拍的图像上传（左右目最好不少于20张）此时回到主页面，即可看到成功导出。把这些误差大的删除即可。
阅读更多2024-12-14
Servlet、omcat服务器架构与工作原理
Servlet是运行在服务器端的Java程序，它的主要职责之一是接收并处理来自客户端（如浏览器）的HTTP请求。当客户端发送一个请求到服务器时，Servlet可以解析请求中的信息，例如请求的URL路径
阅读更多2024-12-14
Vue生命周期钩子函数：深入解析与实践
作为高级Vue前端开发人员，对Vue组件的生命周期钩子函数有着深刻的理解是至关重要的。生命周期钩子函数是指在Vue组件的创建、更新、销毁等过程中，Vue自动调用的一系列方法。通过这些钩子函数，我们可以
阅读更多2024-12-14
安卓开发--使用android studio发布APP
app发布
阅读更多2024-12-14
数据结构与算法学习笔记----拓扑排序
@ author: 明月清了个风。
阅读更多2024-12-14
python 将数据保存到现有的Excel文件的新工作表
out_file = ‘query.xlsx’df1 = pd.DataFrame(out_data)若直接写入：df1.to_excel(out_file, index=False, sheet_n
阅读更多2024-12-14

数据结构第一弹-哈希表

相关文章