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

数据结构小记【Python/C++版】——散列表篇

作者：羊村懒王 | 2024-03-12 09:59:39

赞

踩

数据结构小记【Python/C++版】——散列表篇

一，基础概念

散列表，英文名是hash table，又叫哈希表。

散列表通常使用顺序表来存储集合元素，集合元素以一种很分散的分布方式存储在顺序表中。

散列表是一个键值对(key-item)的组合，由键(key)和元素值(item)组成。键和它对应的元素值基于散列函数(hash function)进行一对一的映射，基于键查找到的元素值也可以称为散列值，查找公式：item = hash(key)。其中item可以是具体的值，也可以是具体的值对应的内存地址，也可以是链表或者链表的指针。

注意，有的教程里面喜欢把键值对称为(key, item)，有的教程里面喜欢把键值对称为(index, value)，其实是相同的意思。

散列表和数组相似的地方在于，都可以基于下标快速的访问数据，数组的下标是索引，散列表的下标是键。

散列表结构在生活中的抽象模型：一个班级所有学生的姓名和对应的学号。

二，散列表的图示结构

图一，key -> hash function -> hash table（key, item）

图二，哈希函数：item = key % 10

三，关于散列函数

最常见的散列函数： 

除数留余法：item = (key + 5) % 10

例如：key=50, item = 5。key = 44, item = 9

好的散列函数具有以下特性：

函数的设计不过于复杂。

大部分情况下，使用相同的键只会查找到同一个值。

键和元素值要均匀随机分布。

基于键查找每个元素值的时间是近似的，而不是查找有的值耗时很长，查找有的值耗时很短。

发生散列冲突的概率极低。

四，散列冲突处理

所谓散列冲突，是指不同的键映射到了相同的散列值。

例如，对于”item = key % 10“的哈希函数，key为12或者22得到的散列值都是2。

方式一，链表法

在链表法中，散列表中的每个key都映射到一个链表。因此，当两个key具有相同的item值时，这两个key都被添加到相同的链表中。

方式二，线性探测法

线性探测法是开放寻址法中的一种，所谓开放寻址，是指如果出现了散列冲突，在散列表中重新找一块儿没被使用过的内存地址，组成新的键值对。

具体操作

基于当前key生成的item值，没有被其他键值对占用时。则该item值可以和key组成键值对来放进散列表中。如果该item值对应了已有的其他的key，则将该key映射到散列表中还没被使用的下一个位置的item值，组成新的键值对来放进散列表中。

对于当前场景，具体步骤为

step.01: 采用item=key%10的方式来获得哈希值。

step.02: 发现采用item= key%10的方式获得的哈希值被别的key占用了，于是采用item=(key+1)%10的方式来获得新的哈希值。

step.03: 发现采用item=(key+1)%10的方式获得的新哈希值没被占用，就将此哈希值作为key的item，生成键值对放入到散列表。否则，继续采用item=(key+2)%10的方式来获得哈希值，以此类推。

例如

根据key=70获得的哈希值也是0。但是那个位置已经被(key=10, item=0)占用了。因此，根据线性探测法，我们将继续找到下一个位置 1。由于该位置暂时未被占用，我们依此生成(key=70, item=1)的键值对。

两种方式对比

五，散列表常见操作

a.插入元素

step1.计算key对应的散列值。

step2.如果散列值不在散列表中，则插入生成新的键值对。

step3.如果散列值已经在散列表中，则发生了散列冲突，return返回或覆盖旧散列值或调用专门处理散列冲突的函数。

b.查找元素

step1.计算key对应的散列值。

step2.如果散列值在散列表中，则查找成功，否则，查找失败。

c.删除元素

对于链接法，执行和链表一样的删除操作。

对于开放寻址法，将被删除节点置为“已删除”标记，查找时跳过此节点，插入时重新覆盖该节点。

六，代码实现

1.Python实现：

  1. class HashTable:
  2.     def __init__(self, size):
  3.         self.size = size
  4.         self.hash_table = self.create_buckets()
  5.  
  6.     def create_buckets(self):
  7.         #存储key用的桶结构
  8.         return [[] for _ in range(self.size)]
  9.  
  10.     def insert_val(self, key, val):
  11.         hashed_key = hash(key) % self.size
  12.         bucket = self.hash_table[hashed_key]
  13.  
  14.         found_key = False
  15.         for index, record in enumerate(bucket):
  16.             record_key, record_val = record
  17.             if record_key == key:
  18.                 found_key = True
  19.                 break
  20.         if found_key:
  21.             #遇到散列冲突时，直接覆盖了旧的值
  22.             bucket[index] = (key, val)
  23.         else:
  24.             bucket.append((key, val))
  25.  
  26.     def get_val(self, key):
  27.         hashed_key = hash(key) % self.size
  28.         bucket = self.hash_table[hashed_key]
  29.  
  30.         found_key = False
  31.         for index, record in enumerate(bucket):
  32.             record_key, record_val = record
  33.             if record_key == key:
  34.                 found_key = True
  35.                 break
  36.         if found_key:
  37.             return record_val
  38.         else:
  39.             return "No record found"
  40.  
  41.     def delete_val(self, key):
  42.         hashed_key = hash(key) % self.size
  43.         bucket = self.hash_table[hashed_key]
  44.  
  45.         found_key = False
  46.         for index, record in enumerate(bucket):
  47.             record_key, record_val = record
  48.             if record_key == key:
  49.                 found_key = True
  50.                 break
  51.         if found_key:
  52.             bucket.pop(index)
  53.         return
  54.  
  55.     #魔法函数，遍历对象中的元素
  56.     def __str__(self):
  57.         return "".join(str(item) for item in self.hash_table)
  58.  
  59. hash_table = HashTable(5)
  60. hash_table.insert_val('key_1', 'value_1')
  61. hash_table.insert_val('key_2', 'value_2')
  62. hash_table.insert_val('key_3', 'value_3')
  63. print(hash_table)
  64.  
  65. print("the value of key_2 is: ", hash_table.get_val('key_2'))
  66. hash_table.delete_val('key_3')
  67. print(hash_table)

运行结果：

  1. [][][('key_3', 'value_3')][('key_1', 'value_1'), ('key_2', 'value_2')][]
  2. the value of key_2 is:  value_2
  3. [][][][('key_1', 'value_1'), ('key_2', 'value_2')][]

2.C++实现：

  1. #include<iostream>
  2. #include <list>
  3. using namespace std;
  4. class Hash
  5. {
  6.     int BUCKET;
  7.     //每个散列值对应的链表
  8.     list<int>* table;
  9. public:
  10.     Hash(int V);  
  11.     //插入元素
  12.     void insertItem(int x);
  13.     //删除元素
  14.     void deleteItem(int key);
  15.     //散列函数
  16.     int hashFunction(int x) {
  17.         return (x % BUCKET);
  18.     }
  19.     void displayHash();
  20. };
  21. Hash::Hash(int b)
  22. {
  23.     this->BUCKET = b;
  24.     table = new list<int>[BUCKET];
  25. }
  26. void Hash::insertItem(int key)
  27. {
  28.     int value = hashFunction(key);
  29.     table[value].push_back(key);
  30. }
  31. void Hash::deleteItem(int key)
  32. {
  33.     //找到key对应的散列值
  34.     int index = hashFunction(key);
  35.     list <int> ::iterator i;
  36.     for (i = table[index].begin();
  37.         i != table[index].end(); i++) {
  38.         if (*i == key)
  39.             break;
  40.     }
  41.     //删除key对应的元素
  42.     if (i != table[index].end())
  43.         table[index].erase(i);
  44. }
  45. void Hash::displayHash() {
  46.     for (int i = 0; i < BUCKET; i++) {
  47.         cout << i;
  48.         for (auto x : table[i])
  49.             cout << " --> " << x;
  50.         cout << endl;
  51.     }
  52. }
  53. int main()
  54. {
  55.     int a[] = { 15, 11, 27, 8, 12 };
  56.     int n = sizeof(a) / sizeof(a[0]);
  57.     Hash h(7);  
  58.     for (int i = 0; i < n; i++)
  59.         h.insertItem(a[i]);
  60.     h.deleteItem(12);
  61.     h.displayHash();
  62.     return 0;
  63. }

运行结果：

  1. 0
  2. 1 --> 15 --> 8
  3. 2
  4. 3
  5. 4 --> 11
  6. 5
  7. 6 --> 27

3.内置数据类型实现

C++内置数据类型：STL标准库中的unordered_map容器

Python内置数据类型：Python字典dict

Demo1：

  1. #include <iostream>
  2. #include <unordered_map>
  3. using namespace std;
  4. int main()
  5. {
  6.        unordered_map<string, double> umap = {
  7.        {"One", 1},
  8.        {"Two", 2},
  9.        {"Three", 3}
  10.        };
  11.  
  12.  
  13.        //insert value
  14.        umap["PI"] = 3.14;
  15.        umap["root2"] = 1.414;
  16.        umap.insert(make_pair("e", 2.718));
  17.        string key = "PI";
  18.        if (umap.find(key) == umap.end())
  19.               cout << key << " not found\n\n";
  20.        else
  21.               cout << "Found " << key << "\n\n";
  22.        unordered_map<string, double>::iterator itr;
  23.        cout << "\nAll Elements : \n";
  24.        for (itr = umap.begin();
  25.               itr != umap.end(); itr++)
  26.        {
  27.               cout << itr->first << " " <<
  28.                       itr->second << endl;
  29.        }
  30. }

运行结果：

  1. Found PI
  2.  
  3. All Elements :
  4. One 1
  5. Two 2
  6. Three 3
  7. PI 3.14
  8. root2 1.414
  9. e 2.718

Demo2：

  1. dict_obj = {"a":1, "b":2, "c":3, "d":4}
  2.  
  3. #打印字典
  4. print(dict_obj['a'])
  5.  
  6. #增加键值对
  7. dict_obj['e'] = 5
  8.  
  9. #修改字典的值
  10. dict_obj['a'] = 21
  11.  
  12. #删除键值对
  13. del dict_obj['d']
  14. print(dict_obj)
  15.  
  16. #清空字典
  17. dict_obj.clear()
  18. print(dict_obj)

运行结果：

  1. 1
  2. {'a': 21, 'b': 2, 'c': 3, 'e': 5}
  3. {}

七，参考阅读

《Problem Solving with Algorithms and Data Structures Using Python, Second Edition》

https://www.softwaretestinghelp.com/hash-table-cpp-programs/

https://www.digitalocean.com/community/tutorials/hash-table-in-c-plus-plus

https://www.geeksforgeeks.org/hash-map-in-python/

https://scanftree.com/programs/cpp/c-program-for-hashing-with-chaining/

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

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

  

闽ICP备14008679号