哈希表
哈希表(hash table)， 也叫散列表，是根据关键码值(key value) 而直接进行访问的数据结构 它通过贝把关键码值映射到表中的一个位置来访问记录，以加快查找的速度。 这个映射函数叫做散列函数(hash function)，存放记录的数组叫做哈希表(或散列表)
Java HashMap
key - value对，key不重复
new HashMap()/ new TreeMap()
map.set(key, value)
map.get(key)
map.has(key)
map.size()
map.clear()
Java HashSet
不重复元素集合
new HashSet()/ new TreeSet()
set.add(value)
set.delete(value)
set.hash(value)
python map
dict
hashmap = {key: value}
python set
set
c++ map
std:unordered_map
std:map
c
Dictonary<TKey, TValue>
Hashtable
StringDictionary
SortedDictionary
源码阅读
- Java hash set
- Java hash map(hash node, tree node, 看懂put、get)
跳表
查询： O(logn) 更新/删除： O(logn) 空间复杂度: O(n)