#! /usr/bin/env python
# -*- coding: utf-8 -*-
"""
@Author:_defined
@Time: 2020/7/9 16:41
@Description: 实现一个hashmap
"""
class LinearMap(object):
"""
桶，链地址法
"""
def __init__(self):
self.items = []
def add(self, k, v):
self.items.append((k, v))
def get(self, key):
for k, v in self.items:
if key == k:
return v
raise KeyError
class BetterMap(object):
def __init__(self, size=16):
self.map = [LinearMap() for _ in range(size)]
def find_map(self, k):
index = hash(k) & (len(self.map)-1)
return self.map[index]
def add(self, k, v):
m = self.find_map(k)
m.add(k, v)
def get(self, k):
m = self.find_map(k)
return m.get(k)
class HashMap(object):
def __init__(self):
self.maps = BetterMap()
self.size = 0
self.max_size = 1 << 30
def resize(self):
if self.max_size < (self.size << 1):
return 0
new_maps = BetterMap(self.size << 1)
for m in self.maps.map:
for k, v in m.items:
new_maps.add(k, v)
self.maps = new_maps
return 1
def get(self, k):
return self.maps.get(k)
def add(self, k, v):
if self.size == int(len(self.maps.map)*0.75):
status = self.resize()
if not status: raise Exception('Maximum space limit exceeded')
self.maps.add(k, v)
self.size += 1
if __name__ == '__main__':
import string
hashmap = HashMap()
for k, v in enumerate(string.ascii_letters):
hashmap.add(k, v)
print(hashmap)
python 实现一个hashmap
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 做一个积极的人编码、改bug、提升自己我有一个乐园，面向编程，春暖花开！ 看似是一个简单的问题，其实里面包含很多的...
- HashMap 原理 以键值对（key-value）的形式存储元素 通过 hashcode() 和 equals(...
- HashMap简介 HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。HashMap ...
