歡迎光臨
每天分享高質量文章

你真的瞭解字典 (Dictionary) 嗎?

(給演算法愛好者加星標,修煉編程內功

 

轉自:碼農阿宇

cnblogs.com/CoderAyu/p/10360608.html

 

從一道親身經歷的面試題說起

半年前,我參加我現在所在公司的面試,面試官給了一道題,說有一個Y形的鏈表,知道起始節點,找出交叉節點.

為了便於描述,我把上面的那條線路稱為線路1,下麵的稱為線路2.

思路1

先判斷線路1的第一個節點的下級節點是否是線路2的第一個節點,如果不是,再判斷是不是線路2的第二個,如果也不是,判斷是不是第三個節點,一直到最後一個.

如果第一輪沒找到,再按以上思路處理線路一的第二個節點,第三個,第四個… 找到為止.

時間複雜度n2,相信如果我用的是這種方法,可肯定被Pass了.

思路2

首先,我遍歷線路2的所有節點,把節點的索引作為key,下級節點索引作為value存入字典中.

然後,遍歷線路1中節點,判斷字典中是否包含該節點的下級節點索引的key,即dic.ContainsKey((node.next) ,如果包含,那麼該下級節點就是交叉節點了.

時間複雜度是n.

那麼問題來了,面試官問我了,為什麼時間複雜度n呢?你有沒有研究過字典的ContainsKey這個方法呢?難道它不是通過遍歷內部元素來判斷Key是否存在的呢?如果是的話,那時間複雜度還是n2才是呀?

我當時支支吾吾,確實不明白字典的工作原理,厚著麵皮說 “不是的,它是通過哈希表直接拿出來的,不用遍歷”,面試官這邊是敷衍過去了,但在我心裡卻留下了一個謎,已經入職半年多了,欠下的技術債是時候還了.

帶著問題來閱讀

在看這篇文章前,不知道您使用字典的時候是否有過這樣的疑問.

  1. 字典為什麼能無限地Add呢?

  2. 從字典中取Item速度非常快,為什麼呢?

  3. 初始化字典可以指定字典容量,這是否多餘呢?

  4. 字典的桶buckets 長度為素數,為什麼呢?

不管您以前有沒有在心裡問過自己這些問題,也不管您是否已經有了自己得答案,都讓我們帶著這幾個問題接著往下走.

從哈希函式說起

什麼是哈希函式?

哈希函式又稱散列函式,是一種從任何一種資料中創建小的數字“指紋”的方法。

下麵,我們看看JDK中Sting.GetHashCode()方法.

public int hashCode() {
       int h = hash;
//hash default value : 0
       if (h == 0 && value.length > 0) {
//value : char storage
           char val[] = value;
           for (int i = 0; i < value.length; i++) {
               h = 31 * h + val[i];
           }
           hash = h;
       }
       return h;
}

可以看到,無論多長的字串,最終都會傳回一個int值,當哈希函式確定的情況下,任何一個字串的哈希值都是唯一且確定的.

當然,這裡只是找了一種最簡單的字符數哈希值求法,理論上只要能把一個物件轉換成唯一且確定值的函式,我們都可以把它稱之為哈希函式.

這是哈希函式的示意圖.

所以,一個物件的哈希值是確定且唯一的!.

字典

如何把哈希值和在集合中我們要的資料的地址關聯起來呢?解開這個疑惑前我來看看一個這樣不怎麼恰當的例子:

有一天,我不小心幹了什麼壞事,警察叔叔沒有逮到我本人,但是他知道是一個叫阿宇的乾的,他要找我肯定先去我家,他怎麼知道我家的地址呢?他不可能在全中國的家庭一個個去遍歷,敲門,問阿宇是你們家的熊孩子嗎?

正常應該是通過我的名字,找到我的身份證號碼,然後我的身份證上登記著我的家庭地址(我們假設一個名字只能找到一張身份證).

阿宇—–> 身份證(身份證號碼,家庭住址)——>我家

我們就可以把由阿宇找到身份證號碼的過程,理解為哈希函式,身份證儲存著我的號碼的同時,也儲存著我家的地址,身份證這個角色在字典中就是 bucket,它起一個橋梁作用,當有人要找阿宇家在哪時,直接問它,準備錯的,字典中,bucket儲存著資料的記憶體地址(索引),我們要知道key對應的資料的記憶體地址,問buckets要就對了.

key—>bucket的過程 ~= 阿宇—–>身份證 的過程.

警察叔叔通過家庭住址找到了我家之後,我家除了住我,還住著我爸,我媽,他敲門的時候,是我爸開門,於是問我爸爸,阿宇在哪,我爸不知道,我爸便問我媽,兒子在哪?我媽告訴警察叔叔,我在書房呢.很好,警察叔叔就這樣把我給逮住了.

字典也是這樣,因為key的哈希值範圍很大的,我們不可能宣告一個這麼大的陣列作為buckets,這樣就太浪費了,我們做法時HashCode%BucketSize作為bucket的索引.

假設Bucket的長度3,那麼當key1的HashCode為2時,它資料地址就問buckets2要,當key2的HashCode為5時,它的資料地址也是問buckets2要的.

這就導致同一個bucket可能有多個key對應,即下圖中的Johon Smith和Sandra Dee,但是bucket只能記錄一個記憶體地址(索引),也就是警察叔叔通過家庭地址找到我家時,正常來說,只有一個人過來開門,那麼,如何找到也在這個家裡的我的呢?我爸記錄這我媽在廚房,我媽記錄著我在書房,就這樣,我就被揪出來了,我爸,我媽,我 就是字典中的一個entry.

果有一天,我媽媽老來得子又生了一個小寶寶,怎麼辦呢?很簡單,我媽記錄小寶寶的位置,那麼我的只能巴結小寶寶,讓小寶寶來記錄我的位置了.

既然大的原理明白了,是不是要看看原始碼,來研究研究代碼中字典怎麼實現的呢?

DictionaryMini

上次在蘇州參加蘇州微軟技術俱樂部成立大會時,有幸參加了蔣金楠 老師講的Asp .net core框架解密,蔣老師有句話讓我印象很深刻,”學好一門技術的最好的方法,就是模仿它的樣子,自己造一個出來”於是他弄了個Asp .net core mini,所以我效仿蔣老師,弄了個DictionaryMini

原始碼放在Github倉庫,有興趣的可以看看:

https://github.com/liuzhenyulive/DictionaryMini

我覺得字典這幾個方面值得瞭解一下:

  1. 資料儲存的最小單元的資料結構

  2. 字典的初始化

  3. 添加新元素

  4. 字典的擴容

  5. 移除元素

字典中還有其他功能,但我相信,只要弄明白的這幾個方面的工作原理,我們也就恰中肯綮,他麽問題也就迎刃而解了.

資料儲存的最小單元(Entry)的資料結構

private struct Entry
{
   public int HashCode;
   public int Next;
   public TKey Key;
   public TValue Value;
}

一個Entry包括該key的HashCode,以及下個Entry的索引Next,該鍵值對的Key以及資料Vaule.

字典初始化

private void Initialize(int capacity)
{
   int size = HashHelpersMini.GetPrime(capacity);
   _buckets = new int[size];
   for (int i = 0; i < _buckets.Length; i++)
   {
       _buckets[i] = -1;
   }
   _entries = new Entry[size];
   _freeList = -1;
}

字典初始化時,首先要創建int陣列,分別作為buckets和entries,其中buckets的index是key的哈希值%size,它的value是資料在entries中的index,我們要取的資料就存在entries中.當某一個bucket沒有指向任何entry時,它的value為-1

另外,很有意思得一點,buckets的陣列長度是多少呢?這個我研究了挺久,發現取的是大於capacity的最小質數.

添加新元素

private void Insert(TKey key, TValue value, bool add)
{
   if (key == null)
   {
       throw new ArgumentNullException();
   }
   //如果buckets為空,則重新初始化字典.
   if (_buckets == null) Initialize(0);
   //獲取傳入key的 哈希值
   var hashCode = _comparer.GetHashCode(key);
   //把hashCode%size的值作為標的Bucket的Index.
   var targetBucket = hashCode % _buckets.Length;
   //遍歷判斷傳入的key對應的值是否已經添加字典中
   for (int i = _buckets[targetBucket]; i > 0; i = _entries[i].Next)
   {
       if (_entries[i].HashCode == hashCode && _comparer.Equals(_entries[i].Key, key))
       {
           //當add為true時,直接丟擲異常,告訴給定的值已存在在字典中.
           if (add)
           {
               throw new Exception("給定的關鍵字已存在!");
           }
           //當add為false時,重新賦值並退出.
           _entries[i].Value = value;
           return;
       }
   }
   //表示本次儲存資料的資料在Entries中的索引
   int index;
   //當有資料被Remove時,freeCount會加1
   if (_freeCount > 0)
   {
       //freeList為上一個移除資料的Entries的索引,這樣能儘量地讓連續的Entries都利用起來.
       index = _freeList;
       _freeList = _entries[index].Next;
       _freeCount--;
   }
   else
   {
       //當已使用的Entry的資料等於Entries的長度時,說明字典里的資料已經存滿了,需要對字典進行擴容,Resize.
       if (_count == _entries.Length)
       {
           Resize();
           targetBucket = hashCode % _buckets.Length;
       }
       //預設取未使用的第一個
       index = _count;
       _count++;
   }
   //對Entries進行賦值
   _entries[index].HashCode = hashCode;
   _entries[index].Next = _buckets[targetBucket];
   _entries[index].Key = key;
   _entries[index].Value = value;
   //用buckets來登記資料在Entries中的索引.
   _buckets[targetBucket] = index;
}

字典的擴容

private void Resize()
{
   //獲取大於當前size的最小質數
   Resize(HashHelpersMini.GetPrime(_count), false);
}
private void Resize(int newSize, bool foreNewHashCodes)
{
   var newBuckets = new int[newSize];
   //把所有buckets設置-1
   for (int i = 0; i < newBuckets.Length; i++) newBuckets[i] = -1;
   var newEntries = new Entry[newSize];
   //把舊的的Enties中的資料拷貝到新的Entires陣列中.
   Array.(_entries, 0, newEntries, 0, _count);
   if (foreNewHashCodes)
   {
       for (int i = 0; i < _count; i++)
       {
           if (newEntries[i].HashCode != -1)
           {
               newEntries[i].HashCode = _comparer.GetHashCode(newEntries[i].Key);
           }
       }
   }
   //重新對新的bucket賦值.
   for (int i = 0; i < _count; i++)
   {
       if (newEntries[i].HashCode > 0)
       {
           int bucket = newEntries[i].HashCode % newSize;
           newEntries[i].Next = newBuckets[bucket];
           newBuckets[bucket] = i;
       }
   }
   _buckets = newBuckets;
   _entries = newEntries;
}

移除元素

//通過key移除指定的item
public bool Remove(TKey key)
{
   if (key == null)
       throw new Exception();
   if (_buckets != null)
   {
       //獲取該key的HashCode
       int hashCode = _comparer.GetHashCode(key);
       //獲取bucket的索引
       int bucket = hashCode % _buckets.Length;
       int last = -1;
       for (int i = _buckets[bucket]; i >= 0; last = i, i = _entries[i].Next)
       {
           if (_entries[i].HashCode == hashCode && _comparer.Equals(_entries[i].Key, key))
           {
               if (last < 0)
               {
                   _buckets[bucket] = _entries[i].Next;
               }
               else
               {
                   _entries[last].Next = _entries[i].Next;
               }
               //把要移除的元素置空.
               _entries[i].HashCode = -1;
               _entries[i].Next = _freeList;
               _entries[i].Key = default(TKey);
               _entries[i].Value = default(TValue);
               //把該釋放的索引記錄在freeList中
               _freeList = i;
               //把空Entry的數量加1
               _freeCount++;
               return true;
           }
       }
   }
   return false;
}

我對.Net中的Dictionary的原始碼進行了精簡,做了一個DictionaryMini,有興趣的可以到我的github查看相關代碼.

https://github.com/liuzhenyulive/DictionaryMini

答疑時間

字典為什麼能無限地Add呢

向Dictionary中添加元素時,會有一步進行判斷字典是否滿了,如果滿了,會用Resize對字典進行自動地擴容,所以字典不會向陣列那樣有固定的容量.

為什麼從字典中取資料這麼快

Key–>HashCode–>HashCode%Size–>Bucket Index–>Bucket–>Entry Index–>Value

整個過程都沒有通過遍歷來查找資料,一步到下一步的目的性時非常明確的,所以取資料的過程非常快.

初始化字典可以指定字典容量,這是否多餘呢

前面說過,當向字典中插入資料時,如果字典已滿,會自動地給字典Resize擴容.

擴容的標準時會把大於當前前容量的最小質數作為當前字典的容量,比如,當我們的字典最終儲存的元素為15個時,會有這樣的一個過程.

new Dictionary()——————->size:3

字典添加低3個元素—->Resize—>size:7

字典添加低7個元素—->Resize—>size:11

字典添加低11個元素—>Resize—>size:23

可以看到一共進行了三次次Resize,如果我們預先知道最終字典要儲存15個元素,那麼我們可以用new Dictionary(15)來創建一個字典.

new Dictionary(15)———->size:23

這樣就不需要進行Resize了,可以想象,每次Resize都是消耗一定的時間資源的,需要把OldEnties  to NewEntries 所以我們在創建字典時,如果知道字典的中要儲存的字典的元素個數,在創建字典時,就傳入capacity,免去了中間的Resize進行擴容.

Tips:

即使指定字典容量capacity,後期如果添加的元素超過這個數量,字典也是會自動擴容的.

為什麼字典的桶buckets 長度為素數

我們假設有這樣的一系列keys,他們的分佈範圍時K={ 0, 1,…, 100 },又假設某一個buckets的長度m=12,因為3是12的一個因子,當key時3的倍數時,那麼targetBucket也將會是3的倍數.

Keys {0,12,24,36,...}
TargetBucket將會是0.
Keys {3,15,27,39,...}
TargetBucket將會是3.
Keys {6,18,30,42,...}
TargetBucket將會是6.
Keys {9,21,33,45,...}
TargetBucket將會是9.

如果Key的值是均勻分佈的(K中的每一個Key中出現的可能性相同),那麼Buckets的Length就沒有那麼重要了,但是如果Key不是均勻分佈呢?

想象一下,如果Key在3的倍數時出現的可能性特別大,其他的基本不出現,TargetBucket那些不是3的倍數的索引就基本不會儲存什麼資料了,這樣就可能有2/3的Bucket空著,資料大量第聚集在0,3,6,9中.

這種情況其實時很常見的。 例如,又一種場景,您根據物件儲存在記憶體中的位置來跟蹤物件,如果你的計算機的位元組大小是4,而且你的Buckets的長度也為4,那麼所有的記憶體地址都會時4的倍數,也就是說key都是4的倍數,它的HashCode也將會時4的倍數,導致所有的資料都會儲存在TargetBucket=0(Key%4=0)的bucket中,而剩下的3/4的Buckets都是空的. 這樣資料分佈就非常不均勻了.

K中的每一個key如果與Buckets的長度m有公因子,那麼該資料就會儲存在這個公因子的倍數為索引的bucket中.為了讓資料盡可能地均勻地分佈在Buckets中,我們要儘量減少m和K中的key的有公因子出現的可能性.那麼,把Bucket的長度設為質數就是最佳選擇了,因為質數的因子時最少的.這就是為什麼每次利用Resize給字典擴容時會取大於當前size的最小質數的原因.

確實,這一塊可能有點難以理解,我花了好幾天才研究明白,如果小伙伴們沒有看懂建議看看這裡.

https://cs.stackexchange.com/questions/11029/why-is-it-best-to-use-a-prime-number-as-a-mod-in-a-hashing-function/64191#64191

最後,感謝大家耐著性子把這篇文章看完,歡迎fork DictionaryMini進行進一步的研究,謝謝大家的支持.

https://github.com/liuzhenyulive/DictionaryMini

赞(0)

分享創造快樂