雜湊表的實現

語言: CN / TW / HK

雜湊表的實現

何為雜湊表

簡單來說,雜湊表是一種儲存結構,它儲存的資料是 key:value 型別的。通過空間換時間的方法來加快查詢速度,具體思想是如下:

  1. 使用一個較大的一維陣列儲存value,這個陣列為Array
  2. 實現一個雜湊函式,使得hash(key)的值在上一步的一維陣列下標範圍內
  3. 如此,對於任意的key:value,使用hash(key),之後就可以知道value在陣列中儲存的下標,存取速度快過線性查詢Array[hash(key)]

雜湊表的注意要點

雜湊函式的選取

由於我們期望,兩個不同的key,hash(key)之後的結果儘量不相同,這樣才能使得雜湊表儲存空間的利用率提高,另一點,雜湊表的空間換時間的主要原因就是他使用了雜湊函式來確定value在陣列中的下標而非普通的線性查詢。那麼,基於以上兩點,雜湊函式的選取就有以下條件:

  • hash函式執行速度不能過慢
  • 對於不同的key(即便兩個key只是字母順序不一致),雜湊函式須儘量保證hash(key)的值不一致

處理雜湊碰撞

由於是無論key的個數有多少,hash(key) 的結果都在一個有限的集合內,即將一個無限的集合對映在一個有限的集合,所以必定會產生不同key但hash(key)結果一樣的情況,這稱為雜湊碰撞,雜湊表的另一要點就是要解決雜湊碰撞。
解決雜湊碰撞一般有以下方法:

  • 開放地址法
  • 再雜湊法
  • 鏈地址法
  • 建立公共溢位區

本文主要將2種解決衝突的方法。

鏈地址法

這種方法可以說是最為簡單的,較為容易理解,並且,這種方法無需擔心初始期間開闢的陣列大小不夠,那麼下面具體來講他。

鏈地址法顧名思義,即使用連結的方式,將產生衝突的元素連結起來,這樣就好比我們初始的數組裡面,存放的都是連結串列的頭節點,如果出現衝突,只需要在連結串列的尾部進行增加節點就好了。

下面貼出一個用Python實現的鏈地址法處理衝突的雜湊表:

# 包含next屬性的節點
class MyLinkDictEntry:
    def __init__(self):
    # -1:Unused 0:Dummy 1:Active
        self.state = -1
        self.hash = None
        self.key = None
        self.value = None
        self.next = None

# 雜湊函式
def hash_func(key,mask):
    hash_val = 0
    for i in key.encode('utf-8'):
        hash_val << 4
        hash_val += i
    return hash_val % mask

# 基礎字典物件
class MyDictObject:
    def __init__(self,length=1024):
        # 生成大小為length的陣列來儲存MyDictEntry
        length = int(length)
        self.mask = length # all
        self.fill = 0 # 0 + 1
        self.used = 0 # 1
        self.data = [MyLinkDictEntry() for _ in range(length)]

    def __str__(self):
        # 列印字典中的值
        s = ''
        s += '{\n'
        for i in [item for item in self.data if item.state == 1]:
            s += i.key + ':' + str(i.value) + '\n'
        s += '}'
        return s


# 鏈地址法的字典
class MyLinkDictObject(MyDictObject):
    def set(self,key, value):
        # 字典增添元素
        hash_val = hash_func(key, self.mask)
        item = self.data[hash_val]
        first_item = None
        while True:
            if item.state == 1 and item.key == key:
                # 該節點被使用並且key一致(更新操作)
                break
            if item.state == 0:
                # 該節點偽刪除 記錄第一個偽刪除的
                first_item = item if first_item == None else first_item
            if item.state == -1:
                # 該結點未使用,增加
                break

            if item.next:
                item = item.next
            else:
                break
        if item.state == 1:
            # 更新操作
            item.key = key
            item.value = value
            item.state = 1
        elif not item.next:
            # 增加操作
            if first_item:
                # 增加到第一個偽刪除節點
                item = first_item
                item.state = 1
                item.key = key
                item.value = value
            else:
                # 增加到最後
                if item.state != -1:
                    item.next = MyLinkDictEntry()
                    item = item.next
                item.state = 1
                item.key = key
                item.value = value
        else:
            raise Exception('未考慮到的情況!')

    def get(self,key):
        # 字典獲取元素
        hash_val = hash_func(key, self.mask)
        item = self.data[hash_val]
        while item:
            if item.state == 1 and item.key == key:
                break
            else:
                item = item.next
        if not item:
            KeyError("沒有這個鍵")
        else:
            return item.value

    def delete(self,key):
        # 字典刪除元素
        hash_val = hash_func(key, self.mask)
        item = self.data[hash_val]
        while item:
            if item.state == 1 and item.key == key:
                break
            else:
                item = item.next
        if not item:
            KeyError("沒有這個鍵")
        else:
            item.state = 0
            self.used -= 1

    def __str__(self):
        # 列印字典中的值
        s = ''
        s += '{\n'
        for item in self.data:
            while item:
                if item.state == 1:
                    s += item.key + ':' + str(item.value) + '\n'
                item = item.next
        s += '}'
        return s