.NET深入了解哈希表和Dictionary

2022 年 11 月 17 日
筆記
.NET, c#, 數據結構與演算法

引子

問題：給定一串數字{1,2,5,7,15,24,33,52},如何在時間複雜度為O(1)下,對數據進行CURD？

數組：我創建一個Length為53的數組，將元素插入相同下標處，是不是就可以實現查找複雜度O(1)了？但是添加修改元素時間複雜度為O(n)了。

鏈表：添加刪除複雜度為O(1)，但是查找時間複雜度為O(n)了。

身為.NETer肯定熟練使用Dictionary和HashSet,這兩個容器的底層就是HashTable，所以帶著對技術濃重的興趣（面試）,所以就從頭到尾梳理一下！

理論

鏈地址法（拉鏈法）

回到問題本身，我們用數組可以實現查找複雜度為O(1),鏈表實現添加刪除複雜度為O(1)，如果我們將兩個合起來，不就可以實現增刪查都為O(1)了么？如何結合呢？

我們先定義一個數組,長度為7（敲黑板，思考下為什麼選7？）,將所有元素對7取余，這樣所有元素都可以放在數組上了，如下圖所示：

如上圖，如果我們將數組中每個下標位置都放成一個鏈條，這樣，複雜度不久降下去了么？

有問題么？沒問題。真沒問題么？有問題……

注意

插入元素是{0,7,14,21,28}怎麼辦？這樣都落在下標為0的鏈條里，時間複雜度不又上去了？針對這種情況，隔壁Java將鏈表優化成了紅黑書，我們.NET呢？往下看。
如果我的數組長度不是7，是2怎麼辦？所有數對2取余，不是1就是0,時間複雜度不又上去了？所以我們對數組長度應該取素數。
如果元素超級多或者特別少，我們的數組長度要固定么？就要動態長度

上邊這種方法學名就叫拉鏈法！

開放地址法

上邊我們聊過拉鏈法（為什麼老想著褲子拉鏈……),拉鏈法是向下開闢新的空間，如果我們橫向開闢空間呢？還是剛才的例子，我們這樣搞一下試試。

線性探測法

我們插完7以後，在插24時，發現下標為2的地方有元素了，於是向後移動一位，發現有空位，於是就插進去了。

上邊這種方法就是線性探測法！

二次聚集（堆積）

聰明的老鳥們，肯定疑惑啦，如果我們繼續添加元素{x%11=4},{y%11=5},此時x，y元素都要往下標6插數據。這樣就導致了原始哈希地址不同的元素要插入同一個地址。即添加同義詞的衝突過程中又添加了非同義詞的衝突。這就是二次聚集。

二次探測法

如果在線性探測法中，我們不依次尋找下一個呢？我們針對”下一個”採取{1 ^ 2,-1 ^ 2,2 ^ 2,-2 ^ 2….}（垃圾編輯器，次方樣式亂了）這樣的步長呢？真聰明！你已經知道二次探測法了！

這……這還能用么？不都亂了么？下標和元素對不上了呀！怎麼去查找元素呢？

別急呀，家人們吶，我們按照這個思路查詢就好了：

查找演算法步驟

1. 給定待查找的關鍵字key,獲取原始應該插入的下標index
2. 如果原始下標index處，元素為空，則所查找的元素不存在
3. 如果index處的元素等於key，則查找成功
4. 否則重複下述解決衝突的過程
  * 按照處理衝突的方法，計算下一個地址nextIndex
  * 若nextIndex為空，則查找元素不存在
  * 若nextIndex等於關鍵詞key，則查找成功

還有要注意的點么？必須有！

注意（敲重點啦）

數組長度必須大於給定元素的長度！
當數組元素快裝滿時，時間複雜度也是O(n)！
如果都裝滿了，就會一直循環找空位，我們應該進行擴容！

理論小結

介面設計

幹活啦，幹活啦，領導嫌查詢效率太低，讓設計一種CURD時間複雜度都為O(n)的數據結構。給了介面。介面如下：

internal interface IDictionary<TK, TV> : IEnumerable<KeyValuePair<TK, TV>>
{
    TV this[TK key] { get; set; }

    int Count { get; }
    /// <summary>
    /// 根據key判斷元素是否存在
    /// </summary>
    /// <param name="key"></param>
    /// <returns></returns>
    bool ContainsKey(TK key);
    /// <summary>
    /// 添加元素
    /// </summary>
    /// <param name="key"></param>
    /// <param name="value"></param>
    void Add(TK key, TV value);
    /// <summary>
    /// 根據key移除元素
    /// </summary>
    /// <param name="key"></param>
    void Remove(TK key);
    /// <summary>
    /// 清除
    /// </summary>
    void Clear();
}

.NET實現線性探測法

實現過程

1. 先來個對象，存儲key和value

對象：KeyValuePair

internal class DictionaryKeyValuePair<TK, TV>
{
    internal TK Key;
    internal TV Value;

    internal DictionaryKeyValuePair(TK key, TV value)
    {
        Key = key;
        Value = value;
    }
}

2. 來個類OpenAddressDictionary，繼承IDictionary介面，就是我們的實現類

實現類：OpenAddressDictionary

/// <summary>
/// 使用線性探測法實現哈希表
/// </summary>
/// <typeparam name="TK"></typeparam>
/// <typeparam name="TV"></typeparam>
public class OpenAddressDictionary<TK, TV> : IDictionary<TK, TV>
{
    //創建一個數組，用來存儲元素
    private DictionaryKeyValuePair<TK, TV>[] hashArray;

    //記錄已插入元素的數量
    public int Count { get; private set; }

    public OpenAddressDictionary(int capacity)
    {
        if (capacity < 0)
            throw new ArgumentOutOfRangeException("初始值容量不能小於0");
        hashArray = new DictionaryKeyValuePair<TK, TV>[capacity];
    }
    public TV this[TK key] {
        get => throw new System.NotImplementedException();
        set => throw new System.NotImplementedException();
    }

    public void Add(TK key, TV value)
    {
        throw new System.NotImplementedException();
    }

    public void Clear()
    {
        throw new System.NotImplementedException();
    }

    public System.Boolean ContainsKey(TK key)
    {
        throw new System.NotImplementedException();
    }

    public IEnumerator<KeyValuePair<TK, TV>> GetEnumerator()
    {
        throw new System.NotImplementedException();
    }

    public void Remove(TK key)
    {
        throw new System.NotImplementedException();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        throw new System.NotImplementedException();
    }
}

3.如何實現查找？跟著上文查找步驟就行

線性探測：查找

/// <summary>
/// 查找，按照上文線性探測查找步驟
/// </summary>
/// <param name="key"></param>
/// <returns></returns>
public bool ContainsKey(TK key)
{
    //1.給定待查找的關鍵字key,獲取原始應該插入的下標index
    var hashCode = GetHash(key);
    var index = hashCode % hashArray.Length;

    //2.如果原始下標index處，元素為空，則所查找的元素不存在
    if (hashArray[index] == null) return false;

    var current = hashArray[index];//當前元素

    /*這個點用來判斷是否走了一整圈*/
    var hitKey = current.Key;

    //4.否則重複下述解決衝突的過程           
    while (current != null)
    {
        //3.如果index處的元素等於key，則查找成功
        if (current.Key.Equals(key)) return true;

        /*這個地方來修改獲取下一個元素位置*/
        index++;

        /*到尾了，但是沒有走完一圈*/
        if (index == hashArray.Length)
            index = 0;

        current = hashArray[index];

        /*走完一圈了，沒找到*/
        if (current != null && current.Key.Equals(hitKey)) break;
    }

    return false;
}

4. 添加

線性探測：添加

/// <summary>
/// 添加元素
/// </summary>
/// <param name="key"></param>
/// <param name="value"></param>
/// <exception cref="Exception"></exception>
public void Add(TK key, TV value)
{
    Grow();
    //1.獲取原始插入位置
    var hashCode = GetHash(key);
    var index = hashCode % hashArray.Length;

    //2.此位置為空，直接插入
    if (hashArray[index] == null)
    {
        hashArray[index] = new DictionaryKeyValuePair<TK, TV>(key, value);
    }
    //3.坑被佔了，去看看下一個
    else
    {
        var current = hashArray[index];
        /*這個點用來判斷是否走了一整圈*/
        var hitKey = current.Key;
        while (current != null)
        {
            if (current.Key.Equals(key)) throw new Exception("重複key");

            /*這個地方來修改獲取下一個元素位置*/
            index++;

            /*到尾了，但是沒有走完一圈*/
            if (index == hashArray.Length)
                index = 0;

            current = hashArray[index];

            /*走完一圈了，沒找到空位*/
            if (current != null && current.Key.Equals(hitKey)) throw new Exception("容器滿了");
        }
        hashArray[index] = new DictionaryKeyValuePair<TK, TV>(key, value);
    }
    Count++;
}
/// <summary>
/// 擴容
/// </summary>
private void Grow()
{
    /*這個地方判斷使用多少擴容*/
    if (hashArray.Length * 0.7 <= Count)
    {
        var orghashArray = hashArray.Length;
        var currentArray = hashArray;

        /*這個地方改變擴容大小的規則*/
        hashArray = new DictionaryKeyValuePair<TK, TV>[hashArray.Length * 2];
        for (var i = 0; i < orghashArray; i++)
        {
            var current = currentArray[i];

            /*舊數組中存在元素，添加到新數組中，Add方法會對Count++,所以加入後要Count--*/
            if (current != null)
            {
                Add(current.Key, current.Value);
                Count--;
            }
        }
        currentArray = null;
    }
}

5. 刪除

線性探測：刪除

/// <summary>
/// 刪除元素key
/// </summary>
/// <param name="key"></param>
/// <exception cref="Exception"></exception>
public void Remove(TK key)
{
    //1.獲取原始插入位置
    var hashCode = GetHash(key);
    var curIndex = hashCode % hashArray.Length;

    //2.此位置為空，無法刪除
    if (hashArray[curIndex] == null) throw new Exception("未找到元素key");

    var current = hashArray[curIndex];

    /*這個點用來判斷是否走了一整圈*/
    var hitKey = current.Key;

    #region 找到待刪除元素
    DictionaryKeyValuePair<TK, TV> target = null;

    while (current != null)
    {
        if (current.Key.Equals(key))
        {
            target = current;
            break;
        }

        /*這個地方來修改獲取下一個元素位置*/
        curIndex++;

        /*到尾了，但是沒有走完一圈*/
        if (curIndex == hashArray.Length)
            curIndex = 0;

        current = hashArray[curIndex];

        /*走完一圈了，沒找到空位*/
        if (current != null && current.Key.Equals(hitKey)) throw new Exception("No such item for given key");
    }

    if (target == null)
    {
        throw new Exception("未找到元素key");
    }
    #endregion  


    //刪除,將當前位置置空
    hashArray[curIndex] = null;

    #region 之前講過刪除，造成元素丟失，所以在此處處理

    curIndex++;

    /*到尾了，但是沒有走完一圈*/
    if (curIndex == hashArray.Length)
        curIndex = 0;

    current = hashArray[curIndex];

    //直到下一個為空的點,到空說明後邊的還沒有被線性探測插入污染
    while (current != null)
    {
        //先刪除
        hashArray[curIndex] = null;

        //重新插入
        Add(current.Key, current.Value);
        Count--;

        curIndex++;

        /*到尾了，但是沒有走完一圈*/
        if (curIndex == hashArray.Length)
            curIndex = 0;

        current = hashArray[curIndex];
    }
    #endregion


    Count--;

    Shrink();
}

/// <summary>
/// 減容
/// </summary>
private void Shrink()
{
    /*這個地方判斷元素在什麼程度算少*/
    if (Count <= hashArray.Length * 0.3 && hashArray.Length / 2 > 0)
    {
        var orghashArray = hashArray.Length;
        var currentArray = hashArray;

        /*這個地方改變擴容大小的規則*/
        hashArray = new DictionaryKeyValuePair<TK, TV>[hashArray.Length / 2];

        for (var i = 0; i < orghashArray; i++)
        {
            var current = currentArray[i];

            /*舊數組中存在元素，添加到新數組中，Add方法會對Count++,所以加入後要Count--*/
            if (current != null)
            {
                Add(current.Key, current.Value);
                Count--;
            }
        }

        currentArray = null;
    }
}

最終程式碼

線性探測：最終程式碼

/// <summary>
/// 使用線性探測法實現哈希表
/// </summary>
/// <typeparam name="TK"></typeparam>
/// <typeparam name="TV"></typeparam>
public class OpenAddressDictionary<TK, TV> : IDictionary<TK, TV>
{
    //創建一個數組，用來存儲元素
    private DictionaryKeyValuePair<TK, TV>[] hashArray;
    //記錄已插入元素的數量
    public int Count { get; private set; }

    public TV this[TK key]
    {
        get => GetValue(key);
        set => SetValue(key, value);
    }

    public OpenAddressDictionary(int capacity)
    {
        if (capacity < 0)
            throw new ArgumentOutOfRangeException("初始值容量不能小於0");
        hashArray = new DictionaryKeyValuePair<TK, TV>[capacity];
    }
    /// <summary>
    /// 清除最簡單
    /// </summary>
    public void Clear()
    {
        if (Count > 0)
            Array.Clear(hashArray, 0, hashArray.Length);
    }

    /// <summary>
    /// 查找，按照上文線性探測查找步驟
    /// </summary>
    /// <param name="key"></param>
    /// <returns></returns>
    public bool ContainsKey(TK key)
    {
        //1.給定待查找的關鍵字key,獲取原始應該插入的下標index
        var hashCode = GetHash(key);
        var index = hashCode % hashArray.Length;

        //2.如果原始下標index處，元素為空，則所查找的元素不存在
        if (hashArray[index] == null) return false;

        var current = hashArray[index];//當前元素

        /*這個點用來判斷是否走了一整圈*/
        var hitKey = current.Key;

        //4.否則重複下述解決衝突的過程           
        while (current != null)
        {
            //3.如果index處的元素等於key，則查找成功
            if (current.Key.Equals(key)) return true;

            /*這個地方來修改獲取下一個元素位置*/
            index++;

            /*到尾了，但是沒有走完一圈*/
            if (index == hashArray.Length)
                index = 0;

            current = hashArray[index];

            /*走完一圈了，沒找到*/
            if (current != null && current.Key.Equals(hitKey)) break;
        }

        return false;
    }

    /// <summary>
    /// 添加元素
    /// </summary>
    /// <param name="key"></param>
    /// <param name="value"></param>
    /// <exception cref="Exception"></exception>
    public void Add(TK key, TV value)
    {
        Grow();
        //1.獲取原始插入位置
        var hashCode = GetHash(key);
        var index = hashCode % hashArray.Length;

        //2.此位置為空，直接插入
        if (hashArray[index] == null)
        {
            hashArray[index] = new DictionaryKeyValuePair<TK, TV>(key, value);
        }
        //3.坑被佔了，去看看下一個
        else
        {
            var current = hashArray[index];
            /*這個點用來判斷是否走了一整圈*/
            var hitKey = current.Key;
            while (current != null)
            {
                if (current.Key.Equals(key)) throw new Exception("重複key");

                /*這個地方來修改獲取下一個元素位置*/
                index++;

                /*到尾了，但是沒有走完一圈*/
                if (index == hashArray.Length)
                    index = 0;

                current = hashArray[index];

                /*走完一圈了，沒找到空位*/
                if (current != null && current.Key.Equals(hitKey)) throw new Exception("容器滿了");
            }
            hashArray[index] = new DictionaryKeyValuePair<TK, TV>(key, value);
        }
        Count++;
    }
    /// <summary>
    /// 刪除元素key
    /// </summary>
    /// <param name="key"></param>
    /// <exception cref="Exception"></exception>
    public void Remove(TK key)
    {
        //1.獲取原始插入位置
        var hashCode = GetHash(key);
        var curIndex = hashCode % hashArray.Length;

        //2.此位置為空，無法刪除
        if (hashArray[curIndex] == null) throw new Exception("未找到元素key");

        var current = hashArray[curIndex];

        /*這個點用來判斷是否走了一整圈*/
        var hitKey = current.Key;

        #region 找到待刪除元素
        DictionaryKeyValuePair<TK, TV> target = null;

        while (current != null)
        {
            if (current.Key.Equals(key))
            {
                target = current;
                break;
            }

            /*這個地方來修改獲取下一個元素位置*/
            curIndex++;

            /*到尾了，但是沒有走完一圈*/
            if (curIndex == hashArray.Length)
                curIndex = 0;

            current = hashArray[curIndex];

            /*走完一圈了，沒找到空位*/
            if (current != null && current.Key.Equals(hitKey)) throw new Exception("No such item for given key");
        }

        if (target == null)
        {
            throw new Exception("未找到元素key");
        }
        #endregion  


        //刪除,將當前位置置空
        hashArray[curIndex] = null;

        #region 之前講過刪除，造成元素丟失，所以在此處處理

        curIndex++;

        /*到尾了，但是沒有走完一圈*/
        if (curIndex == hashArray.Length)
            curIndex = 0;

        current = hashArray[curIndex];

        //直到下一個為空的點,到空說明後邊的還沒有被線性探測插入污染
        while (current != null)
        {
            //先刪除
            hashArray[curIndex] = null;

            //重新插入
            Add(current.Key, current.Value);
            Count--;

            curIndex++;

            /*到尾了，但是沒有走完一圈*/
            if (curIndex == hashArray.Length)
                curIndex = 0;

            current = hashArray[curIndex];
        }
        #endregion


        Count--;

        Shrink();
    }

    /// <summary>
    /// 擴容
    /// </summary>
    private void Grow()
    {
        /*這個地方判斷使用多少擴容*/
        if (hashArray.Length * 0.7 <= Count)
        {
            var orghashArray = hashArray.Length;
            var currentArray = hashArray;

            /*這個地方改變擴容大小的規則*/
            hashArray = new DictionaryKeyValuePair<TK, TV>[hashArray.Length * 2];
            for (var i = 0; i < orghashArray; i++)
            {
                var current = currentArray[i];

                /*舊數組中存在元素，添加到新數組中，Add方法會對Count++,所以加入後要Count--*/
                if (current != null)
                {
                    Add(current.Key, current.Value);
                    Count--;
                }
            }
            currentArray = null;
        }
    }
    /// <summary>
    /// 減容
    /// </summary>
    private void Shrink()
    {
        /*這個地方判斷元素在什麼程度算少*/
        if (Count <= hashArray.Length * 0.3 && hashArray.Length / 2 > 0)
        {
            var orghashArray = hashArray.Length;
            var currentArray = hashArray;

            /*這個地方改變擴容大小的規則*/
            hashArray = new DictionaryKeyValuePair<TK, TV>[hashArray.Length / 2];

            for (var i = 0; i < orghashArray; i++)
            {
                var current = currentArray[i];

                /*舊數組中存在元素，添加到新數組中，Add方法會對Count++,所以加入後要Count--*/
                if (current != null)
                {
                    Add(current.Key, current.Value);
                    Count--;
                }
            }

            currentArray = null;
        }
    }

    private void SetValue(TK key, TV value)
    {
        var index = GetHash(key) % hashArray.Length;

        if (hashArray[index] == null)
        {
            Add(key, value);
        }
        else
        {
            var current = hashArray[index];
            var hitKey = current.Key;

            while (current != null)
            {
                if (current.Key.Equals(key))
                {
                    Remove(key);
                    Add(key, value);
                    return;
                }

                index++;

                //wrap around
                if (index == hashArray.Length)
                    index = 0;

                current = hashArray[index];

                //reached original hit again
                if (current != null && current.Key.Equals(hitKey)) throw new Exception("Item not found");
            }
        }

        throw new Exception("Item not found");
    }

    private TV GetValue(TK key)
    {
        var index = GetHash(key) % hashArray.Length;

        if (hashArray[index] == null) throw new Exception("Item not found");

        var current = hashArray[index];
        var hitKey = current.Key;

        while (current != null)
        {
            if (current.Key.Equals(key)) return current.Value;

            index++;

            //wrap around
            if (index == hashArray.Length)
                index = 0;

            current = hashArray[index];

            //reached original hit again
            if (current != null && current.Key.Equals(hitKey)) throw new Exception("Item not found");
        }

        throw new Exception("Item not found");
    }

    private int GetHash(TK key)
    {
        return Math.Abs(key.GetHashCode());
    }
    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
    //迭代器就不寫了，想了解看我部落格容器欄目
    public IEnumerator<KeyValuePair<TK, TV>> GetEnumerator()
    {
        throw new System.NotImplementedException();
    }
}
internal class DictionaryKeyValuePair<TK, TV>
{
    internal TK Key;
    internal TV Value;

    internal DictionaryKeyValuePair(TK key, TV value)
    {
        Key = key;
        Value = value;
    }
}

.NET實現拉鏈法

實現過程

回想一下，上邊的拉鏈法，每個下標位置放置的是一個鏈條，所以我們先實現一個雙向鏈表

1. 實現一個雙向鏈表

拉鏈法:構建雙向鏈表

internal class DLinkedNode<T>
{
    public T Data;
    public DLinkedNode<T> Next;
    public DLinkedNode<T> Previous;

    public DLinkedNode(T data)
    {
        Data = data;
    }
}

2. 創建一個拉鏈法實體類

拉鏈法:實現類

/// <summary>
/// 拉鏈法：實現類
/// </summary>
/// <typeparam name="TK"></typeparam>
/// <typeparam name="TV"></typeparam>
internal class SeparateChainingDictionary<TK, TV>:IDictionary<TK, TV>
{
    //構建一個數組，數組每個節點都是鏈表
    private DLinkedNode<KeyValuePair<TK, TV>>[] hashArray;
    //已使用數組下標個數
    private int filledBuckets;

    public SeparateChainingDictionary(int capacity) {
        if (capacity < 0)
            throw new ArgumentOutOfRangeException("初始值容量不能小於0");
        hashArray = new DLinkedNode<KeyValuePair<TK, TV>>[capacity];
    }
    public TV this[TK key] { 
        get => throw new NotImplementedException(); 
        set => throw new NotImplementedException(); 
    }

    public int Count => throw new NotImplementedException();

    public void Add(TK key, TV value)
    {
        throw new NotImplementedException();
    }

    public void Clear()
    {
        throw new NotImplementedException();
    }

    public bool ContainsKey(TK key)
    {
        throw new NotImplementedException();
    }

    public void Remove(TK key)
    {
        throw new NotImplementedException();
    }

    public IEnumerator<KeyValuePair<TK, TV>> GetEnumerator()
    {
        throw new NotImplementedException();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        throw new NotImplementedException();
    }
}

3. 拉鏈法：查找

拉鏈法:查找

/// <summary>
/// 查找
/// </summary>
/// <param name="key"></param>
/// <returns></returns>
public bool ContainsKey(TK key)
{
    /*1.獲取原始下標*/
    var index = Math.Abs(key.GetHashCode()) % hashArray.Length;

    /*2.為空即無*/
    if (hashArray[index] == null) return false;

    var current = hashArray[index];

    /*3.遍歷鏈表*/
    while (current != null)
    {               
        if (current.Data.Key.Equals(key)) return true;

        current = current.Next;
    }

    return false;
}

4. 拉鏈法:添加

拉鏈法:添加

/// <summary>
/// 添加
/// </summary>
/// <param name="key"></param>
/// <param name="value"></param>
/// <exception cref="Exception"></exception>
public void Add(TK key, TV value)
{
    Grow();

    var index = Math.Abs(key.GetHashCode()) % hashArray.Length;

    if (hashArray[index] == null)
    {
        hashArray[index] = new DLinkedNode<KeyValuePair<TK, TV>>(new KeyValuePair<TK, TV>(key, value));
        filledBuckets++;
    }
    else
    {
        var current = hashArray[index];

        while (current != null && current.Next != null)
        {
            /*此處可以判斷是重複修改，還是拋異常*/
            if (current.Data.Key.Equals(key)) throw new Exception("重複key");

            current = current.Next;
        }
        if (current.Data.Key.Equals(key)) throw new Exception("重複key");
        current.Next = new DLinkedNode<KeyValuePair<TK, TV>>(new KeyValuePair<TK, TV>(key, value));
    }

    Count++;
}

/// <summary>
/// 擴容
/// </summary>
private void Grow()
{
    if (filledBuckets >= hashArray.Length * 0.7)
    {
        filledBuckets = 0;

        var newBucketSize = hashArray.Length * 2;

        var biggerArray = new DLinkedNode<KeyValuePair<TK, TV>>[newBucketSize];

        for (var i = 0; i < hashArray.Length; i++)
        {
            var item = hashArray[i];

            if (item != null)
            {
                var current = item;

                while (current != null)
                {
                    var next = current.Next;

                    var newIndex = Math.Abs(current.Data.Key.GetHashCode()) % newBucketSize;

                    if (biggerArray[newIndex] == null)
                    {
                        filledBuckets++;
                        biggerArray[newIndex] = current;
                    }

                    var bItem = biggerArray[newIndex];
                    while(bItem.Next != null)
                        bItem = bItem.Next;
                    bItem.Next = current;

                    current = next;
                }
            }
        }

        hashArray = biggerArray;
    }
}

5. 拉鏈法:刪除

拉鏈法:刪除

public void Remove(TK key)
{
    var index = Math.Abs(key.GetHashCode()) % hashArray.Length;

    if (hashArray[index] == null) throw new Exception("未找到key");

    var current = hashArray[index];

    /*查找待刪除元素*/
    DLinkedNode<KeyValuePair<TK, TV>> item = null;
    while (current != null)
    {
        if (current.Data.Key.Equals(key))
        {
            item = current;
            break;
        }
        current = current.Next;
    }

    if (item == null)
    {
        throw new Exception("未找到key");
    }

    /*刪除*/
    if (item.Next == null)
        item = null;
    else
    {
        item.Previous = item.Next; 
        item.Next.Previous =item.Previous ;
        item = null;
    }


    if (hashArray[index] == null)
    {
        filledBuckets--;
    }

    Count--;

    Shrink();
}
private void Shrink()
{
    /*是否減容*/
    if (Math.Abs(filledBuckets - hashArray.Length * 0.3) < 0.1 && hashArray.Length / 2 > 0)
    {
        filledBuckets = 0;
        var newBucketSize = hashArray.Length / 2;

        var smallerArray = new DLinkedNode<KeyValuePair<TK, TV>>[newBucketSize];

        for (var i = 0; i < hashArray.Length; i++)
        {
            var item = hashArray[i];

            if (item != null)
            {
                var current = item;

                /*找到新的存儲點*/
                while (current != null)
                {
                    var next = current.Next;

                    var newIndex = Math.Abs(current.Data.Key.GetHashCode()) % newBucketSize;

                    if (smallerArray[newIndex] == null)
                    {
                        filledBuckets++;
                        smallerArray[newIndex] = current;
                    }

                    var newItem = smallerArray[newIndex];
                    while(newItem.Next != null)
                        newItem = newItem.Next;
                    newItem.Next = current;

                    current = next;
                }
            }
        }

        hashArray = smallerArray;
    }
}

最終程式碼

拉鏈法:最終程式碼


internal class DLinkedNode<T>
{
  public T Data;
  public DLinkedNode<T> Next;
  public DLinkedNode<T> Previous;

  public DLinkedNode(T data)
  {
      Data = data;
  }
}
internal class SeparateChainingDictionary<TK, TV> : IDictionary<TK, TV>
{
//構建一個數組，數組每個節點都是鏈表
private DLinkedNode<KeyValuePair<TK, TV>>[] hashArray;
//已使用數組下標個數
private int filledBuckets;

public SeparateChainingDictionary(int capacity)
{
    if (capacity < 0)
        throw new ArgumentOutOfRangeException("初始值容量不能小於0");
    hashArray = new DLinkedNode<KeyValuePair<TK, TV>>[capacity];
}
public TV this[TK key]
{
    get => throw new NotImplementedException();
    set => throw new NotImplementedException();
}

public int Count { get; private set; }

/// <summary>
/// 添加
/// </summary>
/// <param name="key"></param>
/// <param name="value"></param>
/// <exception cref="Exception"></exception>
public void Add(TK key, TV value)
{
    Grow();

    var index = Math.Abs(key.GetHashCode()) % hashArray.Length;

    if (hashArray[index] == null)
    {
        hashArray[index] = new DLinkedNode<KeyValuePair<TK, TV>>(new KeyValuePair<TK, TV>(key, value));
        filledBuckets++;
    }
    else
    {
        var current = hashArray[index];

        while (current != null && current.Next != null)
        {
            /*此處可以判斷是重複修改，還是拋異常*/
            if (current.Data.Key.Equals(key)) throw new Exception("重複key");

            current = current.Next;
        }
        if (current.Data.Key.Equals(key)) throw new Exception("重複key");
        current.Next = new DLinkedNode<KeyValuePair<TK, TV>>(new KeyValuePair<TK, TV>(key, value));
    }

    Count++;
}

/// <summary>
/// 擴容
/// </summary>
private void Grow()
{
    if (filledBuckets >= hashArray.Length * 0.7)
    {
        filledBuckets = 0;

        var newBucketSize = hashArray.Length * 2;

        var biggerArray = new DLinkedNode<KeyValuePair<TK, TV>>[newBucketSize];

        for (var i = 0; i < hashArray.Length; i++)
        {
            var item = hashArray[i];

            if (item != null)
            {
                var current = item;

                while (current != null)
                {
                    var next = current.Next;

                    var newIndex = Math.Abs(current.Data.Key.GetHashCode()) % newBucketSize;

                    if (biggerArray[newIndex] == null)
                    {
                        filledBuckets++;
                        biggerArray[newIndex] = current;
                    }

                    var bItem = biggerArray[newIndex];
                    while(bItem.Next != null)
                        bItem = bItem.Next;
                    bItem.Next = current;

                    current = next;
                }
            }
        }

        hashArray = biggerArray;
    }
}


public void Clear()
{
    throw new NotImplementedException();
}

/// <summary>
/// 查找
/// </summary>
/// <param name="key"></param>
/// <returns></returns>
public bool ContainsKey(TK key)
{
    /*1.獲取原始下標*/
    var index = Math.Abs(key.GetHashCode()) % hashArray.Length;

    /*2.為空即無*/
    if (hashArray[index] == null) return false;

    var current = hashArray[index];

    /*3.遍歷鏈表*/
    while (current != null)
    {
        if (current.Data.Key.Equals(key)) return true;

        current = current.Next;
    }

    return false;
}

public void Remove(TK key)
{
    var index = Math.Abs(key.GetHashCode()) % hashArray.Length;

    if (hashArray[index] == null) throw new Exception("未找到key");

    var current = hashArray[index];

    /*查找待刪除元素*/
    DLinkedNode<KeyValuePair<TK, TV>> item = null;
    while (current != null)
    {
        if (current.Data.Key.Equals(key))
        {
            item = current;
            break;
        }
        current = current.Next;
    }

    if (item == null)
    {
        throw new Exception("未找到key");
    }

    /*刪除*/
    if (item.Next == null)
        item = null;
    else
    {
        item.Previous = item.Next; 
        item.Next.Previous =item.Previous ;
        item = null;
    }


    if (hashArray[index] == null)
    {
        filledBuckets--;
    }

    Count--;

    Shrink();
}
private void Shrink()
{
    /*是否減容*/
    if (Math.Abs(filledBuckets - hashArray.Length * 0.3) < 0.1 && hashArray.Length / 2 > 0)
    {
        filledBuckets = 0;
        var newBucketSize = hashArray.Length / 2;

        var smallerArray = new DLinkedNode<KeyValuePair<TK, TV>>[newBucketSize];

        for (var i = 0; i < hashArray.Length; i++)
        {
            var item = hashArray[i];

            if (item != null)
            {
                var current = item;

                /*找到新的存儲點*/
                while (current != null)
                {
                    var next = current.Next;

                    var newIndex = Math.Abs(current.Data.Key.GetHashCode()) % newBucketSize;

                    if (smallerArray[newIndex] == null)
                    {
                        filledBuckets++;
                        smallerArray[newIndex] = current;
                    }

                    var newItem = smallerArray[newIndex];
                    while(newItem.Next != null)
                        newItem = newItem.Next;
                    newItem.Next = current;

                    current = next;
                }
            }
        }

        hashArray = smallerArray;
    }
}
public IEnumerator<KeyValuePair<TK, TV>> GetEnumerator()
{
    throw new NotImplementedException();
}

IEnumerator IEnumerable.GetEnumerator()
{
    throw new NotImplementedException();
}
}

Dictionary源碼分析

模擬實現：一個Dictionary，存儲數據{1，’a’},{‘4′,’b’},{5,’c’}

1. 創建一個單鏈表，用來存儲K-V

private struct Entry
{
    public uint hashCode;
    //值為-1，表示是該鏈條最後一個節點
    //值小於-1，表示已經被刪除的自由節點
    public int next;
    public TKey key;     // Key of entry
    public TValue value; // Value of entry
}

2. 創建一個數組當桶，還有一個鏈表數組（核心就這兩個數組）

private int[]? _buckets;
private Entry[]? _entries;

3. 模擬實現插入{1，’a’},{‘4′,’b’},{5,’c’}

初始化

第一次插入{1，’a’}

第二次插入{‘4′,’b’}

第三次插入{5,’c’}

仔細看一下這三個數據的插入，及數據的變化，應該可以理解_buckets和_entries的關係

4.刪除

上邊再講哈希表，包括我們自己實現的程式碼中，刪除一個節點後，都要重新計算後邊的位置。如何解決這個問題呢？我們可以使用Entry的next，來表示是否已經刪除，小於0就表示是自由節點。

關於刪除就這樣幾個變數：

private int _freeList;//最後一個刪除的Entry下標
private int _freeCount;//當前已刪除，但是還未重新使用的節點數量
private const int StartOfFreeList = -3;//幫助尋找自由節點的一個常量

看一下StartOfFreeList和_freeList和Entry.next如何尋找自由節點

刪除時：Entry[i].next=上一層中的StartOfFreeList-_freeList
添加&&_freeCount>0:_freeList=StartOfFreeList – entries[_freeList].next

請看圖理解：

源碼：簡化版（debug理解）

源碼：簡化版可直接運行

public static void Main(string[] args)
{
    Dictionary<int, char> dic = new Dictionary<int, char>();
    dic.TryInsert(1, 'a');
    dic.TryInsert(4, 'b');
    dic.TryInsert(5, 'c');
    dic.Remove(4);
    dic.Remove(5);
    dic.TryInsert(0, 'd');
    dic.TryInsert(1, 'e');
}

public class Dictionary<TKey, TValue>
{
private int[]? _buckets;
private Entry[]? _entries;
private int _count;
private int _freeList;
private int _freeCount;
private int _version;
private const int StartOfFreeList = -3;
public Dictionary()
{
    /*初始值為素數，這裡就不動態了，獲取素數可以使用埃及篩選法*/
    Initialize(7);
}
private int Initialize(int capacity)
{
    int size = capacity;
    int[] buckets = new int[size];
    Entry[] entries = new Entry[size];
    _freeList = -1;
    _buckets = buckets;
    _entries = entries;
    return size;
}

public bool TryInsert(TKey key, TValue value)
{
    Entry[]? entries = _entries;
    uint hashCode = (uint)key.GetHashCode();

    uint collisionCount = 0;
    ref int bucket = ref GetBucket(hashCode);
    int i = bucket - 1; // Value in _buckets is 1-based
    if (typeof(TKey).IsValueType)
    {
        while (true)
        {
            if ((uint)i >= (uint)entries.Length)
            {
                break;
            }

            if (entries[i].hashCode == hashCode && EqualityComparer<TKey>.Default.Equals(entries[i].key, key))
            {
                entries[i].value = value;
                return true;
            }

            i = entries[i].next;

            collisionCount++;
            if (collisionCount > (uint)entries.Length)
            {
                throw new Exception("");
            }
        }
    }
    int index;
    if (_freeCount > 0)
    {
        index = _freeList;
        // Debug.Assert((StartOfFreeList - entries[_freeList].next) >= -1, "shouldn't overflow because `next` cannot underflow");
        _freeList = StartOfFreeList - entries[_freeList].next;
        _freeCount--;
    }
    else
    {
        int count = _count;
        if (count == entries.Length)
        {
            //Resize();
            bucket = ref GetBucket(hashCode);
        }
        index = count;
        _count = count + 1;
        entries = _entries;
    }

    ref Entry entry = ref entries![index];
    entry.hashCode = hashCode;
    entry.next = bucket - 1; // Value in _buckets is 1-based
    entry.key = key;
    entry.value = value; // Value in _buckets is 1-based
    bucket = index + 1;
    _version++;
    return true;
}
public bool Remove(TKey key)
{
    if (key == null) return false;

    if (_buckets != null)
    {
        uint collisionCount = 0;
        uint hashCode = (uint)key.GetHashCode();
        ref int bucket = ref GetBucket(hashCode);
        Entry[]? entries = _entries;
        int last = -1;
        int i = bucket - 1; // Value in buckets is 1-based
        while (i >= 0)
        {
            ref Entry entry = ref entries[i];

            if (entry.hashCode == hashCode && EqualityComparer<TKey>.Default.Equals(entry.key, key))
            {
                if (last < 0)
                {
                    bucket = entry.next + 1; 
                }
                else
                {
                    entries[last].next = entry.next;
                }

                entry.next = StartOfFreeList - _freeList;

                entry.key = default!;

                entry.value = default!;

                _freeList = i;
                _freeCount++;
                return true;
            }
            last = i;
            i = entry.next;
            collisionCount++;
            if (collisionCount > (uint)entries.Length)
            {

            }
        }
    }
    return false;
}
private ref int GetBucket(uint hashCode)
{
    int[] buckets = _buckets!;
    return ref buckets[hashCode % (uint)buckets.Length];
}
private struct Entry
{
    public uint hashCode;
    //值為-1，表示是該鏈條最後一個節點
    public int next;
    public TKey key;     // Key of entry
    public TValue value; // Value of entry
}

Tags: .NET c# 數據結構與演算法

.NET深入了解哈希表和Dictionary

引子

理論

鏈地址法（拉鏈法）

開放地址法

理論小結

介面設計

.NET實現線性探測法

實現過程

最終程式碼

.NET實現拉鏈法

實現過程

最終程式碼

Dictionary源碼分析

1. 創建一個單鏈表，用來存儲K-V

2. 創建一個數組當桶，還有一個鏈表數組（核心就這兩個數組）

3. 模擬實現插入{1，’a’},{‘4′,’b’},{5,’c’}

4.刪除

源碼：簡化版（debug理解）

VirMach 便宜 VPS

QNews

.NET深入了解哈希表和Dictionary

引子

理論

鏈地址法（拉鏈法）

開放地址法

理論小結

介面設計

.NET實現線性探測法

實現過程

最終程式碼

.NET實現拉鏈法

實現過程

最終程式碼

Dictionary源碼分析

1. 創建一個單鏈表，用來存儲K-V

2. 創建一個數組當桶，還有一個鏈表數組（核心就這兩個數組）

3. 模擬實現插入{1，’a’},{‘4′,’b’},{5,’c’}

4.刪除

源碼：簡化版（debug理解）

分享此文：

Related Posts

ADF 第三篇：Integration runtime和 Linked Service

每日三道面試題，通往自由的道路6——JVM

ROSIntegration ROSIntegrationVision與虛幻引擎4（Unreal Engine 4）的配置

少走點彎路：Wiki.js 通過 Generic OAuth2 進行身份驗證

VirMach 便宜 VPS

QNews

熱門搜尋