LeetCode学习笔记- Hash Table 杂凑表- 观念介绍

Github连结

1. Hash Table 是什么?

• 杂凑表，又称为哈希表
• 根据键值(Key)，并透过Hash Function来查询在记忆体储存位置的资料结构
• 其实就是一种资料储存和访问的技术
• 由成对的(key, value)所构成，在Python中，通常使用字典(Dictionary)来实现，一个Key对应一个value，不会同时有多个相同名称的Key
• 主要由Keys、Hash Function和Hash Table所构成，Hash Table由N个buckets所组成，而每个bucket又由M个Slots所构成，每个Slot能够存取一笔数据

2. 实作过程(如下图):

当我们要获取Jack( Keys )的值，我们需要透过Hash Function来计算出Hashing Address(或Home Address)，然后找到Hash Table中对应的Bucket来获取篮球( values )

3. Hash Table的优势

• 主要优点: 执行insert/search/delete/modify的时间复杂度皆为O(1)，也就是不管资料量多大都超级快

(但当Hash Collision发生时，上面的优点不成立)

• Data与排列顺序并没有什么关系，所以搜寻数据时，不需要事先排序
• 由于中间有Hash Function，不了解它做了什么运算，很难取得Data，所以安全性和保密性非常高

4. Hash Table 应用范围

• 数据本身与其排列顺序并无关系
• 没有重复访问值的情况(ex. Jack就是对应篮球)
• 或重复情况下需要统计次数的时候，像是今天Jack可能从体育室拿了好几次篮球，我们要去统计他拿了几次
• 需要在O(1)的时间复杂度下快速地存取DATA时

5. Hash Collision是什么?

不同笔数据，像是(a, b)，经过中间Hash Function的计算后，得到了一样的Hashing Address，就是H(a) = H(b)

6. Python中如何操作Dictionary

• 创建字典: {} 或dict()

 ## 创立字典python_dict = {'x': 1, 'y': 4}
python_dict
{'x': 1, 'y': 4}

• 插入:

 ## 插入新数据python_dict['z'] = 10
python_dict
{'x': 1, 'y': 4, 'z': 10}

• 访问值:

 ## 访问数据print(python_dict.get('z'))
print(python_dict['z'])
10
10

• 删除:

 ## 删除一组数据del python_dict['z']
python_dict
{'x': 1, 'y': 4}

• 判断字典中是否存在某key

 ## 第一种方法print(python_dict.__contains__('z'))
## 第二种方法print('x' in python_dict)
False
True

• 取得一组一组的key和value: for k, v in python_dict.items():

 ## 取得一组一组的key和value
for k, v in python_dict.items():
  print(k)
  print(v)
x
1
y
4

Reference

由于这篇是参考我所学习的课程加上网路资源，再经过自己的消化而来，如果有地方原作者觉得不妥，都请马上与我联系喔，我会马上移除，感谢

https://hiskio.com/courses/319/lectures/15376

https://zh.wikipedia.org/wiki/哈希表

https://blog.kennycoder.io/2020/02/18/资料结构与演算法笔记-Hashing-杂凑原理介绍/