HashMap实现

thisred
2022年03月30日 02:28

一直不懂HashMap的实现，直到看到了一篇博客，才恍然大悟。先简单写几笔，之后再更新。

HashMap的实现是数组加链表。HashMap的主体是个数组，

private Element<TK, TV>[] _objects = { };

数组的查找时间复杂度O(1)，数组里的元素类似这种结构。

class Element<TK, TV>
{
    public TK K;
    public TV V;
    public long HashValue; // key的HashValue
    public Element<TK, TV>? Next; // 下一个节点
}

Next是下一个节点，主体数组下标是k的hash值，HashMap添加的时候，k的hash值处已存在元素，也就是两个元素的hash值相同，那么就加到相同hash值节点的下一个节点上，从而形成个链表。

向HashMap添加元素。（ 注：只是演示个大概意思，代码可能不能运行）

public void Put(TK k, TV v)
{
    var hashCode = k.GetHashCode();// 得到hash值
    var element = new Element<TK, TV>();
    element.HashValue = hashCode;
    if (_objects.Contains<>(hashCode)) // 已经存在元素，那么就加在后一个节点
    {
        var next = _objects[hashCode];
        while (next != null)
        {
            next = next.Next;
        }

        if (next != null) next.Next = element;
        return;
    }

    _objects[hashCode] = element;
}

从HashMap得到一个元素，如果数组中存在那个元素的hash值，那么判断那个元素是否是个链表，也就是hash值相同的一堆元素。如果是个链表，那么就判断k是否相同。添加的时候数组下标是k的hash值，可能两个k的hash值相同。（
注：只是演示个大概意思，代码可能不能运行）

public TV Get(TK k)
{
    var hashCode = k.GetHashCode();
    var element = _objects[hashCode];
    while (element.Next != null && element.HashValue != hashCode && element.K != k)
    {
        element = element.Next;
    }

    return element.V;
}

一个HashMap的好坏主要看Hash函数，如果Hash函数得出来的值都相同，那不就和链表一样了。。。

未完待续~~~

返回顶部