首页 > 其他分享 >散列表(Hash table哈希表)应用案例

散列表(Hash table哈希表)应用案例

时间:2024-10-10 13:22:36浏览次数:9  
标签:word text self Hash 哈希 table counts 列表 散列

文章目录


散列表(Hash table),也叫哈希表,是一种数据结构,它实现了关联数组的概念,即一种能够高效地进行插入、删除和查找键值对(key-value pair)的数据结构。散列表通常由一个数组和一个将键映射到数组索引的函数(散列函数或哈希函数)组成。

散列表基础内容

散列表的基本操作包括:

  • 插入:将一个键值对添加到散列表中。
  • 查找:根据给定的键来获取对应的值。
  • 删除:移除指定键的键值对。

散列表的关键组成部分:

  • 散列函数:用于将键转换为数组中的索引。理想情况下,散列函数应该均匀分布键值对,使得每个桶(bucket)中的元素数量尽可能相同。
  • 处理冲突的方法:因为散列函数可能会将不同的键映射到同一个索引上(这种情况称为冲突)。常见的解决冲突的方法有:
    • 开放地址法:当发生冲突时,在散列表中寻找下一个可用的位置(例如线性探测再散列、二次探测再散列或双重散列)。
    • 链地址法:每个数组位置都存储一个链表或者其它数据结构来保存具有相同哈希值的元素。
  • 负载因子:是散列表中存储的元素数与散列表大小的比值。它影响着散列表的性能,通常当负载因子过高时需要调整散列表大小并重新散列所有元素。

散列表的优点:

  • 平均情况下的时间复杂度为 O(1),即常数时间复杂度,这意味着即使对于非常大的数据集,插入、删除和查找操作也非常快。

散列表的缺点:

  • 需要额外的空间来存储数据,尤其是在负载因子较高时。
  • 如果散列函数选择不当或者处理冲突的方式不够好,性能可能会退化至 O(n),即线性时间复杂度。

散列表在实际应用中非常广泛,几乎所有的现代编程语言都提供了散列表或类似的数据结构作为标准库的一部分。

实现散列表的方法

实现散列表(哈希表)通常涉及到几个关键部分:设计散列函数、处理冲突以及决定何时及如何重新哈希(rehashing)。下面是几种常见的实现方法:

1. 散列函数的设计

散列函数的目标是将输入(键)转换成一个合适的数组索引,并且尽量避免碰撞(不同键产生相同的哈希值)。常用的散列函数设计技术包括:

  • 直接寻址: 当键本身就是整数时,可以直接用作数组索引。
  • 模运算: 常见的做法是对某个较大的素数取模。
  • 位运算: 比如将键的二进制表示右移若干位。
  • 混合运算: 结合加法、减法、乘法、除法等算术运算与位运算。
  • 随机哈希函数: 使用随机选择的哈希函数,以减少特定数据集上的冲突概率。

2. 冲突解决策略

当两个或多个键通过散列函数映射到同一个位置时,就会发生冲突。解决冲突的主要方法有两种:

  • 开放地址法:

    • 线性探测:当发生冲突时,按顺序寻找下一个空闲的位置。
    • 二次探测:使用步长为 1, -1, 2, -2, … 的序列来解决冲突。
    • 双重散列:使用第二个散列函数计算步长。
  • 链地址法:

    • 使用链表或其他动态数据结构(如红黑树)来存储哈希值相同的键值对。

3. 重新哈希

随着散列表中元素的增加,冲突的概率也会增加,这会导致性能下降。为了避免这种情况,可以采用以下策略:

  • 动态调整大小:当负载因子超过某个阈值时(通常是 0.7 或更高),散列表会自动调整其大小,并将现有的元素重新散列到新的数组中。
  • 二次哈希:在某些情况下,可能需要多次重新哈希来找到一个合适的数组大小。

实现示例

下面是一个简单的散列表实现的例子,使用 Python 编写,采用链地址法处理冲突:

class HashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]

    def _hash(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self._hash(key)
        bucket = self.table[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # 更新已存在的键
                break
        else:
            bucket.append((key, value))

    def find(self, key):
        index = self._hash(key)
        bucket = self.table[index]
        for k, v in bucket:
            if k == key:
                return v
        return None

    def remove(self, key):
        index = self._hash(key)
        bucket = self.table[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                return v
        return None

这个简单的实现仅用于说明目的,并没有包含所有可能的功能,比如重新哈希、更复杂的散列函数等。实际应用中,可能需要考虑更多细节以提高效率和可靠性。

具体案例展示

下面给出一个具体的案例来展示如何使用散列表(哈希表)来解决问题。这里我们来看一个简单的问题:统计一段文本中各个单词出现的次数。

假设我们有一段文本如下:

Hello world, this is a simple example of a hashtable.
This example will demonstrate how hashtables work.

我们的目标是从这段文本中统计每个单词出现的次数。我们可以使用散列表来存储每个单词及其出现的次数。

步骤:

  1. 文本预处理:去除标点符号,将所有字母转换为小写,以便统一处理。
  2. 构建散列表:使用散列表来存储单词及其计数。
  3. 统计单词出现次数:遍历文本中的每一个单词,并更新散列表中的计数。

Python 实现:

import string

class WordCounter:
    def __init__(self):
        self.word_counts = dict()

    def count_words(self, text):
        # 文本预处理
        translator = str.maketrans('', '', string.punctuation)
        cleaned_text = text.translate(translator).lower()
        
        # 分割单词
        words = cleaned_text.split()
        
        # 统计单词
        for word in words:
            if word in self.word_counts:
                self.word_counts[word] += 1
            else:
                self.word_counts[word] = 1

    def get_word_counts(self):
        return self.word_counts

# 示例文本
text = """
Hello world, this is a simple example of a hashtable.
This example will demonstrate how hashtables work.
"""

# 创建一个 WordCounter 对象
word_counter = WordCounter()

# 计算单词频率
word_counter.count_words(text)

# 输出结果
word_counts = word_counter.get_word_counts()
for word, count in word_counts.items():
    print(f"{word}: {count}")

输出结果:

hello: 1
world: 1
this: 2
is: 1
a: 2
simple: 1
example: 2
of: 1
hashtable: 1
will: 1
demonstrate: 1
how: 1
work: 1

在这个例子中,我们首先创建了一个 WordCounter 类,该类包含一个字典 word_counts 用来存储单词及其出现次数。然后,我们定义了一个 count_words 方法来处理文本,并统计每个单词的出现次数。最后,我们输出了每个单词及其对应的计数。

这个例子展示了如何使用散列表来有效地统计文本中单词的出现次数。实际应用中,还可以进一步优化代码,例如处理更多的边缘情况,或者使用更高效的文本处理技术。

继续扩展之前的示例,使其更加完整和健壮。我们将添加一些额外的功能,例如处理多种语言的文本、忽略常见的停用词(stopwords)、以及提供一个更详细的统计报告。

扩展功能:

  1. 多语言支持:处理多种语言的文本,例如中文和其他非英语文本。
  2. 停用词处理:忽略常见的停用词,如 “the”, “is”, “and” 等。
  3. 详细的统计报告:输出每个单词的出现次数,并提供最常见的前 N 个单词。

Python 实现:

import string
from collections import Counter

class WordCounter:
    def __init__(self, stopwords=None):
        self.word_counts = {}
        self.stopwords = stopwords or set(["the", "is", "and", "a", "an", "of", "in", "to", "it"])

    def preprocess_text(self, text):
        # 移除标点符号并将文本转换为小写
        translator = str.maketrans('', '', string.punctuation)
        cleaned_text = text.translate(translator).lower()
        return cleaned_text

    def tokenize(self, text):
        # 将文本分割成单词列表
        return text.split()

    def count_words(self, text):
        # 预处理文本
        cleaned_text = self.preprocess_text(text)
        
        # 分割单词
        words = self.tokenize(cleaned_text)
        
        # 统计单词
        for word in words:
            if word not in self.stopwords:
                if word in self.word_counts:
                    self.word_counts[word] += 1
                else:
                    self.word_counts[word] = 1

    def get_word_counts(self):
        return self.word_counts

    def top_n_words(self, n=10):
        # 获取最常见的前 N 个单词
        return Counter(self.word_counts).most_common(n)

# 示例文本
text = """
Hello world, this is a simple example of a hashtable.
This example will demonstrate how hashtables work.
"""

# 创建一个 WordCounter 对象
word_counter = WordCounter()

# 计算单词频率
word_counter.count_words(text)

# 输出结果
word_counts = word_counter.get_word_counts()
print("Word counts:")
for word, count in word_counts.items():
    print(f"{word}: {count}")

# 输出最常见的前 N 个单词
top_words = word_counter.top_n_words(5)
print("\nTop 5 words:")
for word, count in top_words:
    print(f"{word}: {count}")

输出结果:

Word counts:
hello: 1
world: 1
this: 2
simple: 1
example: 2
hashtable: 1
will: 1
demonstrate: 1
how: 1
work: 1

Top 5 words:
this: 2
example: 2
hello: 1
world: 1
simple: 1

新增功能解释:

  1. 多语言支持:虽然这个例子主要处理英文文本,但你可以通过修改 preprocess_text 方法来适应其他语言。例如,对于中文文本,可以使用结巴分词(jieba)库来分词。

  2. 停用词处理:我们定义了一个 stopwords 属性,并在初始化时可以传入自定义的停用词列表。默认情况下,我们忽略了一些常见的英文停用词。

  3. 详细的统计报告:除了输出每个单词的出现次数外,我们还提供了一个 top_n_words 方法来获取最常见的前 N 个单词。

进一步扩展:

如果需要进一步扩展,可以考虑以下方面:

  • 多语言分词器:集成第三方库(如 jieba 对于中文)来支持多种语言的分词。
  • 文本清洗:增加更多的文本清洗步骤,如去除数字、URLs 等。
  • 词形还原:将单词还原为其基本形式(例如,将 “running” 转换为 “run”)。
  • 多线程处理:对于大量文本数据,可以使用多线程或多进程来加速处理速度。

这些扩展可以使你的文本分析工具更加完善,适用于更广泛的场景。

标签:word,text,self,Hash,哈希,table,counts,列表,散列
From: https://blog.csdn.net/qqrrjj2011/article/details/142818979

相关文章

  • 基于 iptables 的防火墙方案
    基于iptables的防火墙方案假设两台主机A(172.29.100.100)和B(10.100.100.100),iptables规则应用于A机器上.允许两台主机互通-AINPUT-s10.100.100.100-jACCEPT-AINPUT-s0.0.0.0/0-jDROP允许A访问B,反向禁止-AINPUT-mstate--stateESTABLISHE......
  • 记录一道面试题(哈希表 稀疏矩阵)
    题目:有一个游戏中的三维地图,是由i,j,k三个轴组成的三维网络。每个立方体由不同的种类代表,比如空气,水,沙子,泥土。地图上方的空气方块,不会经常变动且数量占大多数,下方是各种类型的方块,会经常相互转换(水变沙子,沙子变泥土等)。问题:请你实现一个存储该地图的方案(地图方块和对应类型)。要......
  • 通过AI绘画工具(stable diffusion)来赚钱,真是太爽了!
    在当今数字化时代,人工智能(AI)的应用已经无所不在。最新的AI绘画生成工具称为StableDifusion,它能够根据用户输入的文本描述生成相应的图像。这一技术的出现为社交媒体内容创作者、插画师、平面设计师等带来了无限的可能性,同时也开启了新的赚钱机会。在抖音等社交平台上,许多灵......
  • 普通人如何利用Stable Diffusion赚钱,普通人的AI绘图赚钱神器
    在当今快速发展的人工智能技术中,Stable-Diffusion凭借其卓越的图像生成能力已经成为内容创作领域的佼佼者。它不仅显著降低了艺术创作的门槛,让更多人能够享受创作的乐趣,更为创作者们打开了新的赚钱方式。下面我们一起探讨如何利用Stable-Diffusion实现艺术与商业的共赢。......
  • 【JS】哈希法解决两数之和
    思路使用哈希法:需要快速查询一个元素是否出现过,或者一个元素是否在集合里时本题需要一个集合来存放我们遍历过的元素,然后在遍历数组的时候去询问这个集合,符合要求的某元素是否遍历过,也就是是否出现在这个集合。因为要返回下标,所以使用Map集合,key存放元素值,value存放元素下......
  • 【模板】树哈希
    https://peehs-moorhsum.blog.uoj.ac/blog/7891题目描述对一棵树求hash值,以判断两棵树是否同构。有有根树和无根树两个版本。solution找一个随机函数\(f\)(可以选xor-shift),然后每个点的子树的哈希值如下计算:\[h_u=1+\sum_{v}f(h_v)\]这是有根树的情况,对于无根树,1.可以换......
  • Rust 中的 HashMap 实战指南:理解与优化技巧
    Rust中的HashMap实战指南:理解与优化技巧在Rust编程中,HashMap是一个强大的键值对数据结构,广泛应用于数据统计、信息存储等场景。在本文中,我们将通过三个实际的代码示例,详细讲解HashMap的基本用法以及如何在真实项目中充分利用它。此外,我们还将探讨Rust的所有权系统对Ha......
  • 洛谷 P7469 [NOI Online 2021 提高组] 积木小赛(字符串哈希)
    题目传送门解题思路读题后,我们可以发现,字母串  只能从两边删除,于是我们可以枚举一个区间 ,然后在字母串  中匹配(可以用指针来进行匹配),同时可以做字符串哈希去重。注意如果怕被卡,可以用双模哈希;记得开longlong代码#include<bits/stdc++.h>usingnamespacestd;......
  • java中Set的介绍与实现:HashSet、LinkedHashSet、TreeSet
    在Java中,Set是Collection接口的一个子接口,它是一个不包含重复元素的集合,且通常不保证维护元素的有序或迭代顺序。Set接口主要用于确保集合中每个元素的唯一性。Set接口的主要方法:booleanadd(Ee):将指定的元素添加到此集合中(如果它尚未在集合中)。booleanremove(Objec......
  • python3常用库之哈希hashlib和hmac使用
    hashlibimporthashlib#MD5是最常见的哈希算法,速度很快,生成结果是固定的128bit/16字节,通常用一个32位的16进制字符串表示。md5=hashlib.md5()md5.update("hello".encode())print(md5.hexdigest())#5d41402abc4b2a76b9719d911017c592#数据量很大时分块多次调用up......