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 Add(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函数得出来的值都相同，那就和链表一样了。

如何解决Hash冲突

哈希冲突是指不同的键值映射到哈希表的同一个位置上，这会导致查找和插入操作的性能降低。常见的解决哈希冲突的方法有以下几种：

1. 链地址法（Chaining）：将哈希表中每个位置视为一个桶，如果发生哈希冲突，就将冲突的元素添加到该位置对应的桶中。这种方法需要在每个桶中维护一个链表或其他数据结构来存储冲突的元素。链地址法相对简单，但是需要额外的内存来存储链表。
2. 开放地址法（Open Addressing）：如果发生哈希冲突，就从当前位置开始依次探查下一个位置，直到找到一个空位置。探查的方法可以是线性探查、二次探查、双重哈希等。开放地址法不需要额外的内存来存储链表，但是在负载因子较高时，容易产生聚集效应，导致性能下降。
3. 建立公共溢出区（Overflow Area）：将哈希表中所有的冲突元素都放到一个公共的溢出区中，当发生冲突时，就将冲突元素存放在溢出区中。这种方法的优点是实现简单，但是需要额外的空间来存储溢出区。

在实际使用中，需要根据具体的场景和数据特点来选择合适的解决哈希冲突的方法。例如，如果数据量较大且分布较为均匀，可以选择开放地址法；如果数据量较小或者分布较为集中，可以选择链地址法或建立公共溢出区。同时，还可以通过调整哈希表的大小和负载因子来进一步优化性能。