我做彩票网站开发彩票网站搭建,做收钱的网站要什么条件,班级优化大师下载安装,地方门户网站推广方案点击上方蓝色小字#xff0c;关注“码农小黑屋”重磅干货#xff0c;第一时间送达今天这篇文章给大家讲讲hashmap#xff0c;这个号称是所有Java工程师都会的数据结构。为什么说是所有Java工程师都会呢#xff0c;因为很简单#xff0c;他们不会这个找不到工作。几乎所有面… 点击上方蓝色小字关注“码农小黑屋”重磅干货第一时间送达今天这篇文章给大家讲讲hashmap这个号称是所有Java工程师都会的数据结构。为什么说是所有Java工程师都会呢因为很简单他们不会这个找不到工作。几乎所有面试都会问基本上已经成了标配了。在今天的这篇文章当中我们会揭开很多谜团。比如为什么hashmap的get和put操作的复杂度是甚至比红黑树还要快hashmap和hash算法究竟是什么关系hashmap有哪些参数这些参数分别是做什么用的hashmap是线程安全的吗我们怎么来维护hashmap的平衡呢让我们带着疑问来看看hashmap的基本结构。基本结构hashmap这个数据结构其实并不难它的结构非常非常清楚我用一句话就可以说明其实就是邻接表。虽然这两者的用途迥然不同但是它们的结构是完全一样的。说白了就是一个定长的数组这个数组的每一个元素都是一个链表的头结点。我们把这个结构画出来大家一看就明白了。headers是一个定长的数组数组当中的每一个元素都是一个链表的头结点。也就是说根据这个头结点我们可以遍历这个链表。数组是定长的但是链表是变长的所以如果我们发生元素的增删改查本质上都是通过链表来实现的。这个就是hashmap的基本结构如果在面试当中问到你可以直接回答它本质上就是一个元素是链表的数组。hash的作用现在我们搞明白了hashmap的基本结构现在进入下一个问题这么一个结构和hash之间有什么关系呢其实也不难猜我们来思考一个场景。假设我们已经拥有了一个hashmap现在新来了一份数据需要存储。上图当中数组的长度是6也就是说有6个链表可供选择那么我们应该把这个新来的元素放在哪个链表当中呢你可能会说当然是放在最短的那个这样链表的长度才能平衡。这样的确不错但是有一个问题这样虽然存储方便了但是读取的时候却有很大的问题。因为我们存储的时候知道是存在最短的链表里了但是当我们读取的时候我们是不知道当初哪个链表最短了很有可能整个结构已经面目全非了。所以我们不能根据这种动态的量来决定节点的放置位置必须要根据静态的量来决定。这个静态的量就是hash值我们都知道hash算法的本质上是进行一个映射运算将一个任意结构的值映射到一个整数上。我们的理想情况是不同的值映射的结果不同相同的值映射的结果相同。也就是说一个变量和一个整数是一一对应的。但是由于我们的整数数量是有限的而变量的取值是无穷的那么一定会有一些变量虽然它们并不相等但是它们映射之后的结果是一样的。这种情况叫做hash碰撞。在hashmap当中我们并不需要理会hash碰撞因为我们并不追求不同的key能够映射到不同的值。因为我们只是要用这个hash值来决定这个节点应该存放在哪一条链表当中。只要hash函数确定了只要值不变计算得到的hash值也不会变。所以我们查询的时候也可以遵循这个逻辑找到key对应的hash值以及对应的链表。在Python当中由于系统提供了hash函数所以整个过程变得更加方便。我们只需要两行代码就可以找到key对应的链表。hash_key hash(key) % len(self.headers)linked_list self.headers[hash_key]get、put实现明白了hash函数的作用了之后hashmap的问题就算是解决了大半。因为剩下的就是一个在链表当中增删改查的问题了比如我们要通过key查找value的时候。当我们通过hash函数确定了是哪一个链表之后剩下的就是遍历这个链表找到这个值。这个函数我们可以实现在LinkedList这个类当中非常简单就是一个简单的遍历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链表的节点查询逻辑有了之后hashmap的查询逻辑也就有了。因为本质上只做了两件事一件事根据hash函数的值找到对应的链表第二件事就是遍历这个链表找到这个节点。我们也很容易实现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 nodeget方法实现了之后写出put方法也一样水到渠成因为put方法逻辑和get相反。我们把查找换成添加或者是修改即可def put(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 randomclass Node: def __init__(self, key, val, prevNone, succNone): 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 Noneclass HashMap: def __init__(self, capacity16, load_factor5): 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喜欢本篇内容请点个“在看”
