+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2019-07(1)

2019-08(109)

2019-09(120)

2019-10(17)

2019-11(1)

Python底层实现一个简易的HashMap(dict)

发布于2020-09-28 20:12     阅读(645)     评论(0)     点赞(25)     收藏(4)


0

1

2

3

4

5

6

7

8


前前言

在上一片文章中写了对比Python、Java、JavaScript中list, dict的使用,dict就是一个映射集合,在Java中有类似的是HashMap。

上篇文章只是讲了dict的语法层面,只是讲到dict如何增删改查,基本没什么技术含量,这篇文章深入理解Python中的dict(HashMap)底层原理,并且手动封装写一个简易的HashMap(dict).

前言

Python中有一种基础数据结构叫做dict, dict是多个key-value 映射组成的。

在Java中有一个非常类似的工具类,叫做HashMap,也是很多个key-value映射组成的。

python中的dict是作为一种基础数据类型,底层的实现是用C/C++写的,是看不到源码的。而Java中的HashMap是通过基本数据类型封装而成的。

我们也可以使用Python中的基本数据类型封装一个HashMap(不用dict)。

HashMap的作用

HashMap的存在是为了快速访问,通过key可以快速访问到value,并且时间复杂度是O(1)。

那么怎样通过key查找value可以快速查找呢?

学数据结构时学过数组和链表两种线性表,数组可以通过下标随机访问,时间复杂度是O(1),而链表需要遍历来访问,时间复杂度是O(n)。

如果key-value键值对是简单的线性排列,如下:

或者:

那么通过key访问value必须要遍历整个列表,时间复杂度是O(n)。

那么有没有办法可以通过key快速访问到value呢?

这就是hash表。

Hash表原理

能做到随机访问的数据结构只有数组,通过数组下标可以访问内容,时间复杂度是O(1)。

那么现在是需要通过key来访问value,可以把key-value键值对放到特定的数组位置中让key和数组下标有关联,也就是通过key可以计算出数组下标,那么给定一个key,可以迅速定位到value在数组那个元素。

这就是Hash表通过key访问value时间复杂度为O(1)的原理。

Java中HashMap的实现原理

Java中的HashMap结构是这样的:

首先初始化了一个数组,放入key-value键值对时,先计算key的Hash值,再将hash值计算得到数组下标,然后放入数组中(其实是将引用给了数组)。

如果两个元素key经过hash计算,再计算得到数组下标相同(这也叫Hash冲突),那么一个数组节点不可能放两个元素,因此就在该数组节点再放一个链表,将冲突的元素放入链表中

JDK1.7处理Hash冲突是使用的这种链表的方式,而JDK 1.8是使用链表+红黑树的形式,因为加入链表过长,也需要一个个元素遍历,效率也不高。

要想实现一个HashMap,有一下几点要考虑:

  1. 怎样通过Hash值计算得到数组下标?
  2. Hash冲突怎样处理?(使用链表处理用头插法还是尾插法?)
  3. 链表过长怎么办?扩容?如何扩容?

对于问题1,通过Hash值计算出数组下标,这就需要计算出来的结果很平均,而且不能越界。 常规方法可以是取余数,比如数组长度为N,Hash值是x,那么下标应该是x%N。但是取余数效率不高,JDK中使用的是位运算:

static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
}

这里有个条件是数组长度必须是2的幂次,因为这样才可以通过位运算得到正确结果。
而这个位运算为什么可以达到效果呢? 因为length是2的幂,也就是最高位是1,其他低位都是0,而length-1就所有位都是1,然后使用&运算,就把h的低位取了出来,然后结果的范围是比length小的。
比如:length = 16,h = 20

length :    0001 0000
length-1:   0000 1111
h :         0001 0100
length&h:   0000 0100   ==  4

对于问题2,JDK1.7中处理Hash冲突是使用的链表,将冲突元素放入到链表中去,并且是使用的头插法插入元素。

对于问题3, 当Hash表中冲突元素过多,链表很长时,那么访问效率就会很慢(因为链表需要都遍历一遍),就需要扩容,将链表变短,让元素在Hash表中更加分散一些。
根据JDK1.7 HashMap的源码,数组默认初始长度是16,当HashMap中元素达到一个阈值,就会扩容,JDK 1.7中这个阈值是默认是75%,当元素个数达到75%时就会扩容。

使用Python实现HashMap

Talk is cheap, show me the code.

这里我仿照JDK1.7中的HashMap源码进行改写了一下,简化了一些地方,实现了一个Python版本的HashMap。

"""
    Entry表示一个Key-value键值对节点,在Python中的dict里面叫做items。
"""
class Entry():
    def __init__(self, hash = 0, key = 0, value = 0, next = None):
        self.hash = hash
        self.key = key
        self.value = value
        self.next = next


class HashMap():
    """
        初始化默认HashMap的容量是16,加载因子是0.75,也就是阈值是16 * 0.75 = 12,就会扩容
    """
    def __init__(self, capacity = 16, load_factor = 0.75):
        self.__capacity = capacity # HashMap的容量
        self.__load_factor = load_factor # 加载因子, 
        self.__table = [None for i in range(capacity)] # 创建一个空数组
        self.__size = 0 # HashMap中节点总数量
        self.__threshold = capacity * load_factor # HashMap的阈值,超过这个阈值需要扩容
    """
        重写“toString()”方法,这样可以直接输出HashMap
    """
    def __str__(self):
        result = "{"
        count = 0
        for i in range(len(self.__table)):
            if (self.__table[i] != None):
                result += str(self.__table[i].key)
                result += ":"
                result += str(self.__table[i].value)
                if (count != self.__size - 1):
                    count += 1
                    result += ", "

        result += "}"
        return result
    

    """
        根据hash后的值 和 capacity, 得到下标
    Parameters:
		hash: 将key进行hash得到的Hash值
        capacity: 当前数组的长度
	Returns:
		index:数组下标,表示该元素应该放到哪个数组中去

    """
    def __index_for(self, hash, capacity):
        return hash & (self.__capacity - 1)
    """
        扩容后,将旧的list中的链表节点转移到新的list中去
    Parameters:
        new_table: 新创建的Hash表
    Retures: None
    """
    def __transfer(self, new_talbe):
        new_capacity = len(new_talbe)
        for e in self.__table:
            while (None != e):
                next = e.next
                i = self.__index_for(e.hash, new_capacity)
                e.next = new_talbe[i]
                new_talbe[i] = e
                e = next


    """
        扩容, 创建一个新的hash表,容量是new_capacity
        Parameters:
            new_capacity: 新Hash表的容量
    """
    def __resize(self, new_capacity):
        old_table = self.__table
        old_capacity = len(old_table)
        new_talbe = [Entry() for x in range(new_capacity)]
        __transfer(new_talbe)
        self.__table = new_talbe
        self.__threshold = self.__load_factor * self.__capacity

    """
        创建一个节点, 并且将节点使用头插法添加到链表中去
    """
    def __create_entry(self, hash, key, value, bucketIndex):
        e = self.__table[bucketIndex]
        self.__table[bucketIndex] = Entry(hash, key, value, e)
        self.__size += 1

    """
        通过计算key和hash值,将键值对放入到Hash表中去
    """
    def __add_entry(self, hash, key, value, bucket_index):
        # 如果元素过多,就需要扩容
        if ((self.__size >= self.__threshold) and (None != self.__table[bucket_index])):
            __resize(2 * len(self.__table)) # 将容量扩容成两倍
            hash = hash(key)
            bucket_index = self.__index_for(hash, len(self.__table))
        
        self.__create_entry(hash, key, value, bucket_index)

    """
        将key-value pair放入HashMap中
    """
    def put(self, key, value):
        h = hash(key)
        i = self.__index_for(h, self.__capacity)
        e = self.__table[i]
        while (e != None):
            k = e.key

            # 如果key在HashMap中已经存在了
            # 那么就把新的value覆盖旧的value,并且把旧的value返回出来
            if (e.hash == h and (k == key)):
                old_value = e.value
                e.value = value
                return old_value

            e = e.next

        self.__add_entry(h, key, value, i)
        return None
    
    """
        删除某个节点(Entry)
    """
    def __remove_entry_for_key(self, key):
        if (self.__size == 0): return None
        h = hash(key)
        i = self.__index_for(h, len(self.__table))
        prev = self.__table[i]
        e = prev

        while (e != None):
            next = e.next
            k = e.key
            if((e.hash == h) or k == key):
                self.__size -= 1
                if (prev == e):
                    self.__table[i] = next
                else :
                    prev.next = next
                return e
            prev = e
            e = next
        return e
    

    def remove(self, key):
        e = self.__remove_entry_for_key(key)
        if (e == None):return None
        else: return e.value
    
    """
        get方法,通过key,得到value
    """
    def get(self, key):
        entry = self.__get_entry(key)
        if (entry == None):return None
        else: return entry.value


    """
        通过key,找到那个节点
    """
    def __get_entry(self, key):
        if(self.__size == 0):return None
        h = hash(key)
        e = self.__table[self.__index_for(h, len(self.__table))]
        while(e != None):
            k = e.key
            if ((e.hash == h) and e.key == k):
                return e
            e = e.next
        return None            

测试:

person = HashMap()
person.put('name', 'Jackson')
person.put('sex', 'male')
person.put('age','19')
print(person) # 输出完整信息
person.remove('age')
print(person) # 输出name和sex

输出:

{age:19, name:Jackson, sex:male}
{name:Jackson, sex:male}

总结:

Python虽然方便,很多高层的数据结构可以直接使用,但是看不到底层原理和细节,这是我不喜欢Python的一个方面。

这篇简要的讲了Java中的HashMap的实现原理,原理比较简单,但是通过代码写出来还有有难度的,JDK的HashMap源码中还是有很多不错的算法的,很值得研究。

原文链接:https://blog.csdn.net/weixin_43414715/article/details/108831139

0

1

2

3

4

5

6



所属网站分类: 技术文章 > 博客

作者:你太美丽

链接: https://www.pythonheidong.com/blog/article/550958/4b52c2484a98f3f94877/

来源: python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

25 0
收藏该文
已收藏

评论内容:(最多支持255个字符)