首页 / PYTHON / Map的python实现
Map的python实现
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Map的python实现,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2763字,纯文字阅读大概需要4分钟。
内容图文
概念
Python中的Dict是一种使用最为普遍的数据结构,特别是数据之间具有关联关系时。上一博文提到了hash function和hash table的概念,现在来用代码实现HashTable。
我们通过两个list来分别存储key和value,这就要求两个list的大小一致,在对应的index上分别存储key和value。实现HashTable最重要的两个方法是set和get方法,如果通过Class来实现,则需要实现特殊方法__setitem__和__getitem__。这样就可以通过索引来取值。
构造方法
class HashTable:
def __init__(self):
self.size = 11
self.slots = [None] * self.size
self.data = [None] * self.size
确定一个HashTable的长度,并且存储key(slots)和value(data)的list也保持大小一致,且都初始化为None。
hash_function和rehash方法
def hash_function(self, key, size):
return key % size
def rehash(self, old_hash, size):
return (old_hash + 1) % size
通过hash_function方法确定key在hash table中的索引位置,通过rehash消除collision(不同的key经过hash function计算得到相同的index)。
set方法
def set(self, key, value):
hash_value = self.hash_function(key, len(self.slots))
if self.slots[hash_value] is None:
self.slots[hash_value] = key
self.data[hash_value] = value
else:
if self.slots[hash_value] == key:
self.data[hash_value] = value
else:
next_slot = self.rehash(hash_value, len(self.slots))
while self.slots[next_slot] is not None and self.slots[
next_slot] != key:
next_slot = self.rehash(next_slot, len(self.slots))
if self.slots[next_slot] is None:
self.slots[next_slot] = key
self.data[next_slot] = value
else:
self.data[next_slot] = value
set方法的逻辑是:先通过hash function计算key的hash值,然后在保存key的slots(list)中查找对应位置的值是否存在,若不存在,则在该位置保存key,在data(list)中保存key对应的value。
若在slots对应的位置处恰好为key,则update其value。反之,若在slots对应的位置处不为key,则说明发生了collision(数据冲突),那么我们通过rehash方法继续hash,找到一个空余的位置,将该键值对(key和value)放入该位置或仅更新其value。
get方法
def get(self, key):
start_slot = self.hash_function(key, len(self.slots))
position = start_slot
data = None
while self.slots[position] is not None:
if self.slots[position] == key:
data = self.data[position]
break
else:
position = self.rehash(position, len(self.slots))
if position == start_slot:
break
return data
get方法较为简单,也是先获取hash值,然后查找slots在该hash值处所对应的值是否存在,若存在,则判断保存的key是否和要查找的key相等,若相等则返回该值,若不相等则说明发生collision,则使用rehash继续查找。记住,rehash方法必须有一个判断机制,用以判断是否遍历完整个hash table(循环一圈,回到初次hash值)。
__setitem__和__getitem__方法 ##
def __getitem__(self, key):
return self.get(key)
def __setitem__(self, key, value):
self.put(key, value)
这两个方法主要是类似Pyhton字典中的set和get语法,如dic[key] = value。
总结:上述实践仅仅是一个简单的demo。实际对应hash table的大小,hash function的实现有各个各样的方法,在这里仅起到一个抛砖引玉的作用。
内容总结
以上是互联网集市为您收集整理的Map的python实现全部内容,希望文章能够帮你解决Map的python实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。