《犬夜叉镜中的梦幻城》
今天，这篇文章介绍了hashmap，它被称为所有Java工程师都可以做到的数据结构。 为什么所有的Java工程师都能做，因为很简单，他们做不到这个就找不到工作。 大多数面试都会被问到，基本上是标准装备。
今天的这篇文章会揭开很多谜题。 例如，为什么hashmap的get和put操作的复杂性比红黑树还要快呢？ hashmap和hash算法到底是什么关系？ hashmap有哪些参数？ 这些参数分别用于什么？ hashmap是线程安全的吗？ 如何维持hashmap的平衡？
带着疑问看看hashmap的基本结构吧。
基本结构
hashmap这个数据结构其实并不难。 其结构非常清晰。 一句话可以说明，其实是旁边的桌子。 这两者的用途差异很大，但其结构完全相同。 简言之，它是一个固定长度的数组，此数组中的每个元素都是链表的第一个节点。 我们画了这个结构，大家一看就知道了。
headers是固定长度的数组，数组中的每个元素都是链表的第一个节点。 也就是说，这个头部节点允许我们遍历这个链表。 虽然数组是固定长度的，但链表很长，因此在发生元素添加和删除重新评估时，本质上是通过链表实现的。
这是hashmap的基本结构。 面试时问的话，你可以直接回答。 它本质上是链表元素的数组。
混洗的作用
现在我们了解了hashmap的基本结构。 现在进入下一个问题。 这种结构和hash之间有什么关系呢？
实际上，想想场景吧。 假设你已经有了hashmap。 现在需要保存新数据。 上图中的数组长度为6。 也就是说，可以选择六个链表。 那么，应该把这个新元素放在哪个链表里呢？
当然你可能会说放在最短的地方，这样链表的长度就可以平衡了。 这个确实不错，但有一个问题。 这样存储就方便了，但读取时有很大的问题。 因为我们保存的时候知道存在最短的链表，但是我们读取的时候不知道哪个链表是最短的，整个结构很可能发生了变化。 因此，不能凭借这样的动态量来确定节点的放置位置，而是要凭借静态量来确定。
该静态量为hash值。 据了解，混列算法本质上是进行映射运算，将任意结构的值映射为整数。 理想情况下，不同值映射的结果不同，相同值映射的结果相同。 也就是说，变量和整数是一一对应的。 然而，由于我们的整数数目是有限的，并且变量所取的值是无限的，所以它们不相等，但是映射后的结果必须有相同的变量。 这叫做hash碰撞。
hashmap不要求不同的key可以映射到不同的值，因此不需要忽略hash碰撞。 因为您只需要使用此哈希值来确定此节点应该存储在哪个链表中。 确定散列函数后，只要值不变，计算中得到的散列值也不会变化。 所以我们查的时候也可以按照这个逻辑，找到key对应的散列值和对应的链表。
在Python中，整个过程更方便，因为系统提供了散列函数。 可以在两行代码中找到与key对应的链表。
hash_key=hash(key ) %len ) self.headers ) ) ) ) ) ) ) )。
linked _ list=self.headers [ hash _ key ] get，put实现
知道hash函数的作用后，即使hashmap的问题解决了大半。 因为剩下的是在链表中添加和删除检查的问题。 例如，在key中查找value时。 用hash函数决定是哪个链表后，剩下的就是遍历这个链表找到这个值。
可以在名为LinkedList的类中实现此函数。 非常简单。 也就是说，是简单的遍历。
efget_by_key(self，key ) :
cur=self.head.succ
while cur！=self.tail:
if cur.key==key:
返回cur
cur=cur.succ
返回无
有链表的节点查询逻辑，也有hashmap的查询逻辑。 因为本质上只做了两件事，所以第一个是根据散列函数的值找到对应的链表，第二个是遍历这个链表找到这个节点。
我们也很容易做到：
defget(self，key ) :
hash_key=self.get_hash_key(key )
linked _ list=self.headers [ hash _ key ]
node=linked _ list.get _ by _ key (key )
返回节点
get方法实现后，导出put方法也是如此。 因为put方法的逻辑与get相反。 我们只需要添加或修改搜索：
efput(self，key，val ) :
>node = self.get(key)# 如果能找到，那么只需要更新即可
if node is not None:
node.val = val
else:
# 否则我们在链表当中添加一个节点
node = Node(key, val)
linked_list.append(node)复杂度的保障
get和put都实现了，整个hashmap是不是就实现完了？很显然没有，因为还有一件很重要的事情我们没有做，就是保证hashmap的复杂度。
我们简单分析一下就会发现，这样实现的hashmap有一个重大的问题。就是由于hashmap一开始的链表的数组是定长的，不管这个数组多长，只要我们存储的元素足够多，那么每一个链表当中分配到的元素也就会非常多。我们都知道链表的遍历速度是 ，这样我们还怎么保证查询的速度是常数级呢？
除此之外还有另外一个问题，就是hash值倾斜的问题。比如明明我们的链表有100个，但是我们的数据刚好hash值大部分对100取模之后都是0。于是大量的数据就会被存储在0这个桶当中，导致其他桶没什么数据，就这一个桶爆满。对于这种情况我们又怎么避免呢？
其实不论是数据过多也好，还是分布不均匀也罢，其实说的都是同一种情况。就是至少一个桶当中存储的数据过多，导致效率降低。针对这种情况，hashmap当中设计了一种检查机制，一旦某一个桶当中的元素超过某个阈值，那么就会触发reset。也就是把hashmap当中的链表数量增加一倍，并且把数据全部打乱重建。这个阈值是通过一个叫做load_factor的参数设置的，当某一个桶当中的元素大于load_factor * capacity的时候，就会触发reset机制。
我们把reset的逻辑加进去，那么put函数就变成了这样：
def put(self, key, val):
hash_key = self.get_hash_key(key)
linked_list = self.headers[hash_key]
# 如果超过阈值
if linked_list.size >= self.load_factor * self.capacity:
# 进行所有数据reset
self.reset()
# 对当前要加入的元素重新hash分桶
hash_key = self.get_hash_key(key)
linked_list = self.headers[hash_key]
node = linked_list.get_by_key(key)
if node is not None:
node.val = val
else:
node = Node(key, val)
linked_list.append(node)
reset的逻辑也很简单，我们把数组的长度扩大一倍，然后把原本的数据一一读取出来，重新hash分配到新的桶当中即可。
def reset(self):
# 数组扩大一倍
headers = [LinkedList() for _ in range(self.capacity * 2)]
cap = self.capacity
# capacity也扩大一倍
self.capacity = self.capacity * 2
for i in range(cap):
linked_list = self.headers[i]
nodes = linked_list.get_list()
# 将原本的node一个一个填入新的链表当中
for u in nodes:
hash_key = self.get_hash_key(u.key)
head = headers[hash_key]
head.append(u)
self.headers = headers
其实这里的阈值就是我们的最大查询时间，我们可以把它近似看成是一个比较大的常量，那么put和get的效率就有保障了。因为插入了大量数据或者是刚好遇到了hash不平均的情况我们就算是都解决了。
细节和升华
如果你读过JDK当中hashmap的源码，你会发现hashmap的capacity也就是链表的数量是2的幂。这是为什么呢？
其实也很简单，因为按照我们刚才的逻辑，当我们通过hash函数计算出了hash值之后，还需要将这个值对capacity进行取模。也就是hash(key) % capacity，这一点在刚才的代码当中也有体现。
这里有一个小问题就是取模运算非常非常慢，在系统层面级比加减乘慢了数十倍。为了优化和提升这个部分的性能，所以我们使用2的幂，这样我们就可以用hash(key) & (capacity - 1)来代替hash(key) % capacity，因为当capacity是2的幂时，这两者计算是等价的。我们都知道位运算的计算速度是计算机当中所有运算最快的，这样我们可以提升不少的计算效率。
最后聊一聊线程安全，hashmap是线程安全的吗？答案很简单，当然不是。因为里面没有任何加锁或者是互斥的限制，A线程在修改一个节点，B线程也可以同时在读取同样的节点。那么很容易出现问题，尤其是还有reset这种时间比较长的操作。如果刚好在reset期间来了其他的查询，那么结果一定是查询不到，但很有可能这个数据是存在的。所以hashmap不是线程安全的，不可以在并发场景当中使用。
最后，我们附上hashmap完整的实现代码：
import random
class Node:
def __init__(self, key, val, prev=None, succ=None):
self.key = key
self.val = val
# 前驱
self.prev = prev
# 后继
self.succ = succ
def __repr__(self):
return str(self.val)
class LinkedList:
def __init__(self):
self.head = Node(None, 'header')
self.tail = Node(None, 'tail')
self.head.succ = self.tail
self.tail.prev = self.head
self.size = 0
def append(self, node):
# 将node节点添加在链表尾部
prev = self.tail.prev
node.prev = prev
node.succ = prev.succ
prev.succ = node
node.succ.prev = node
self.size += 1
def delete(self, node):
# 删除节点
prev = node.prev
succ = node.succ
succ.prev, prev.succ = prev, succ
self.size -= 1
def get_list(self):
# 返回一个包含所有节点的list，方便上游遍历
ret = []
cur = self.head.succ
while cur != self.tail:
ret.append(cur)
cur = cur.succ
return ret
def get_by_key(self, key):
cur = self.head.succ
while cur != self.tail:
if cur.key == key:
return cur
cur = cur.succ
return None
class HashMap:
def __init__(self, capacity=16, load_factor=5):
self.capacity = capacity
self.load_factor = load_factor
self.headers = [LinkedList() for _ in range(capacity)]
def get_hash_key(self, key):
return hash(key) & (self.capacity - 1)
def put(self, key, val):
hash_key = self.get_hash_key(key)
linked_list = self.headers[hash_key]
if linked_list.size >= self.load_factor * self.capacity:
self.reset()
hash_key = self.get_hash_key(key)
linked_list = self.headers[hash_key]
node = linked_list.get_by_key(key)
if node is not None:
node.val = val
else:
node = Node(key, val)
linked_list.append(node)
def get(self, key):
hash_key = self.get_hash_key(key)
linked_list = self.headers[hash_key]
node = linked_list.get_by_key(key)
return node.val if node is not None else None
def delete(self, key):
node = self.get(key)
if node is None:
return False
hash_key = self.get_hash_key(key)
linked_list = self.headers[hash_key]
linked_list.delete(node)
return True
def reset(self):
headers = [LinkedList() for _ in range(self.capacity * 2)]
cap = self.capacity
self.capacity = self.capacity * 2
for i in range(cap):
linked_list = self.headers[i]
nodes = linked_list.get_list()
for u in nodes:
hash_key = self.get_hash_key(u.key)
head = headers[hash_key]
head.append(u)
self.headers = headers