HashMap实现

一直不懂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函数得出来的值都相同,那不就和链表一样了。。。

未完待续~~~

返回顶部