前前言

在上一片文章中写了对比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