国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

散列表結構 字典與集合

Bamboy / 964人閱讀

摘要:散列表結構字典與集合散列表散列表結構是字典和集合的一種實現方式。使用散列表存儲數據時,通過一個散列函數將鍵映射為一個數字,這個數字范圍是到列表長度。即使使用一個高效的散列函數,仍然存在將兩個鍵映射為同一個值的可能,這種現象稱為碰撞。

散列表結構 字典與集合 散列表

散列表(Hash Table)結構是字典(Dictionary)和集合(Set)的一種實現方式。散列算法的作用是盡可能快地在數據結構中找到一個值。在散列表上插入、刪除和取用數據都非常快,但是對于查找操作來說卻效率地下

散列表是基于數組進行設計的,數組的長度是預先設定,如有需要可隨時增加。所有元素根據和該元素對應的鍵,保存在數組的特定位置。使用散列表存儲數據時,通過一個散列函數將鍵映射為一個數字,這個數字范圍是0到列表長度。散列函數的選擇依賴于鍵的數據類型,在此我們對鍵的hash值對數組長度區余的方法。散列表的數組究竟應該有多大?這是編寫散列函數時必須要考慮的。對散列表大小的限制,通常數組的長度應該是一個質數。

理想情況下,散列函數會將每個鍵值映射為唯一的數組索引,然而,鍵的數量是無限的,散列表的長度是有限的,一個理想的目標是讓散列函數盡量將鍵均勻地映射到散列表中。即使使用一個高效的散列函數,仍然存在將兩個鍵映射為同一個值的可能,這種現象稱為碰撞(collision)。當碰撞發生時,我們需要方案去解決。

分離鏈接:實現散列表底層數組中,每個數組元素是一個新的數據結構,比如另一個數組(二維數組),這樣就能存儲多個鍵了。即使兩個鍵散列后的值相同,依然被保存在同樣的位置,只不過它們在第二個數組中的位置不一樣罷了。

線性探查:當發生碰撞時,線性探測法檢測散列表的下一個位置是否為空。如果為空,就將數據存入該位置;如果不為空,則繼續檢查下一個位置,直到找到一個空的位置為止。

負載因子:如果我們持續往散列表中添加數據空間會不夠用。負載因子是已使用的空間比散列表大小的值。比如,散列表大小為13,已使用空間位8,負載因子位0.62。通常當負載因子超過0.8時,就要新開辟空間并重新散列了。

散列表的操作:

方法 操作
put 向散列表添加新鍵值,或更新鍵的值
remove 從散列表刪除鍵值
get 返回鍵索引到的值
# python3
class HashTable:
    def __init__(self, size=11):
        self._keys = [None] * size
        self._values = [None] * size
        self._length = 0

    # 獲取負載因子
    @property
    def _load_factor(self):
        return self._length / float(len(self._keys))

    # 散列函數
    def _hash_func(self, key):
        l = len(self._keys)
        idx = abs(hash(key)) % l
        # 獲取空索引
        while self._keys[idx] is not None and 
                self._keys[idx] != key:
            idx = (idx + l + 1) % l
        return idx

    def put(self, key, value):
        idx = self._hash_func(key)
        # 更新
        if self._keys[idx] == key:
            self._values[idx] = value
        # 添加
        elif self._keys[idx] is None:
            self._keys[idx] = key
            self._values[idx] = value
            self._length += 1
            # 檢查負載因子
            if self._load_factor >= 0.8:
                self._rehash()

    def get(self, key):
        idx = self._hash_func(key)
        if self._keys[idx] == key:
            return self._values[idx]
        return None

    def remove(self, key):
        idx = self._hash_func(key)
        if self._keys[idx] == key:
            self._keys[idx] = None
            self._values[idx] = None
            self._length -= 1
        elif self._keys[idx] is None:
            self._values[idx] = None
        else:
            return -1

    # 重新散列,擴展大小
    def _rehash(self):
        old_keys = self._keys
        old_value = self._values
        new_size = len(self._keys) * 2
        self._keys = [None] * new_size
        self._values = [None] * new_size
        self._length = 0
        for idx in range(len(old_keys)):
            if old_keys[idx] is not None:
                self.put(old_keys[idx], old_value[idx])

    def length(self):
        return self._length
字典

散列表的基本方法就是字典常用的方法,在此可以繼承散列表類的方法,然后完善其他的字典支持的方法。

字典的操作:

方法 操作
keys 返回所有鍵
values 返回所有值
items 返回所有鍵值對
# python3
class Dict(HashTable):
    def keys(self):
        return [key for key in self._keys if key is not None]

    def values(self):
        return [value for value in self._values if value is not None]

    def items(self):
        return [(self._keys[idx], self._values[idx])
                for idx in range(0, len(self._keys))
                if self._keys[idx] is not None]

    def __iter__(self):
        return iter(self.keys())

    def __len__(self):
        return self.length()

    def __getitem__(self, key):
        return self.get(key)

    def __setitem__(self, key, value):
        self.put(key, value)

    def __contains__(self, key):
        idx = self._hash_func(key)
        return self._keys[idx] is not None
集合

集合是一種包含不同元素的數據結構。集合中的元素被稱為成員。集合的兩個重要特性:首先,集合中的成員是無序的;其次:集合中不允許相同的成員存在。

集合的定義:

不包含任何成員的集合稱為空集,包含一切可能成員的集合稱為全集

如果兩個和的成員完全相同,則稱兩個集合相等。

如果一個集合中所有的成員都屬于另一個集合,則前一集合稱為后一集合的子集

集合的運算:

并集:將兩個集合中的成員進行合并,得到一個新集合。

交集:兩個集合中共同存在的成員組成一個新的集合。

補集:屬于一個集合而不屬于另一個集合的成員組成的集合。

其實集合也是個散列表,散列表有鍵和值,在這里我們把值設置位True即可。具體實現如下。

集合的操作:

方法 操作
put 向集合添加成員。
remove 從集合移除成員。
union 接收一個集合進行并集運算返回結果
intersection 接收一個集合進行交集運算返回結果
difference 接收一個集合進行補集運算返回結果
# python3
class Set(HashTable):
    def put(self, key):
        return super(Set, self).put(key, value=True)

    # 并集運算
    def union(self, other):
        if isinstance(other, Set):
            temp = other
            for key in self._keys:
                temp.put(key)
            return temp
        else:
            raise TypeError

    # 交集運算
    def intersection(self, other):
        if isinstance(other, Set):
            temp = Set()
            for key in self._keys:
                if key in other:
                    temp.put(key)
            return temp
        else:
            raise TypeError()

    # 補集運算
    def difference(self, other):
        if isinstance(other, Set):
            temp = Set()
            for key in self._keys:
                if key not in other:
                    temp.put(key)
            return temp
        else:
            raise TypeError()

    def __or__(self, other):
        return self.union(other)

    def __and__(self, other):
        return self.intersection(other)

    def __sub__(self, other):
        return self.difference(other)

    def __len__(self):
        return self._length

    def __iter__(self):
        for key in self._keys:
            if key is not None:
                yield key

    def __contains__(self, key):
        idx = self._hash_func(key)
        return self._keys[idx] is not None

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/44817.html

相關文章

  • Python中的字典集合

    摘要:若對于關鍵字集合中的任一個關鍵字,經散列函數映象到地址集合中任何一個地址的概率是相等的,則稱此類散列函數為均勻散列函數,這就是使關鍵字經過散列函數得到一個隨機的地址,從而減少沖突。 導語:本文章記錄了本人在學習Python基礎之數據結構篇的重點知識及個人心得,打算入門Python的朋友們可以來一起學習并交流。 本文重點: 1、掌握常見的字典創建,查詢,判別方法;2、了解字典中的defa...

    hqman 評論0 收藏0
  • 學習數據結構算法之字典列表

    摘要:小結實現了字典和哈希表感覺沒有想象中那么困難,當然這還是開始。 本系列所有文章:第一篇文章:學習數據結構與算法之棧與隊列第二篇文章:學習數據結構與算法之鏈表第三篇文章:學習數據結構與算法之集合第四篇文章:學習數據結構與算法之字典和散列表第五篇文章:學習數據結構與算法之二叉搜索樹 字典 不是新華字典哦,這里的字典也稱作_映射_,是一種數據結構,跟set集合很相似的一種數據結構,都可以用來...

    Heier 評論0 收藏0
  • Javascript的數據結構算法(二)

    摘要:基本版的散列表實現在散列表中我們通過散列函數來確定鍵值對的關系。的實現具體看的數據結構與算法一。散列函數不超過數組的長度下面兩個值相同源碼地址的數據結構與算法二源碼 1集合 1.1集合的實現 集合是由一組無序且唯一(即不能重復)的項組成的。這個數據結構使用了與有限集合相同 的數學概念,但應用在計算機科學的數據結構中。 集合中常用方法列表: add(value):向集合中添加一個新的...

    jlanglang 評論0 收藏0
  • 每周一練 之 數據結構算法(Dictionary 和 HashTable)

    摘要:什么是散列表和散列函數哈希表,也叫散列表,是根據關鍵碼值而直接進行訪問的數據結構。根據鍵值從散列表中移除值。請實現散列表將和存在一個對象中即可定義一個包含和屬性的類并分配到散列表。 showImg(https://segmentfault.com/img/remote/1460000019005270); 這是第五周的練習題,上周忘記發啦,這周是復習 Dictionary 和 Hash...

    eternalshallow 評論0 收藏0
  • 每周一練 之 數據結構算法(Dictionary 和 HashTable)

    摘要:什么是散列表和散列函數哈希表,也叫散列表,是根據關鍵碼值而直接進行訪問的數據結構。將字典的所有鍵名以數組的形式返回。根據鍵值從散列表中移除值。這是第五周的練習題,上周忘記發啦,這周是復習 Dictionary 和 HashTable。 下面是之前分享的鏈接: 1.每周一練 之 數據結構與算法(Stack) 2.每周一練 之 數據結構與算法(LinkedList) 3.每周一練 之 數據結構...

    ingood 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<