【学习笔记】哈希表、字典、集合知识点
哈希表 Hash Table
-
哈希表，也叫散列表，是根据关键码值（key-value)而直接进行访问的数据结构。 - 通过将关键码值映射到表中的一个位置来访问记录，以加快查找的速度。
- 这个映射函数叫做散列函数（Hash Function),存放记录的数组叫做哈希表（或者叫散列）
哈希函数如下图：
哈希冲突：不同的要存储的数据经过哈希函数返回相同的值，称为哈希冲突
哈希冲突如下图：
工程实践：
- 电话号码簿
- 用户信息表
- 缓存 LRU Cache
- 键值对存储 Redis
一般认为 HashTable 添加/删除元素的时间复杂度为 O(1),特殊情况是哈希表开的比较小，出现了哈希冲突，这时候可以通过把相同的值拉一个链表解决。
HashTable 具体到应用层面：
1.字典dict:key-value对，key不重复,value 可以重复
2.集合set :不重复元素的集合