python哈希錶

集合Set

集合,簡稱集。由任意個元素構成的集體。高級語言都實現了這個非常重要的數據結構類型。

Python中,它是可變的、無序的、不重複的元素的集合。

初始化

  • set() -> new empty set object
  • set(iterable) -> new set object
s1 = set()
s2 = set(range(5))
s3 = set([1, 2, 3])
s4 = set('abcdabcd')
s5 = {} # 這是什麼?
s6 = {1, 2, 3}
s7 = {1, (1,)}
s8 = {1, (1,), [1]} # ?

元素性質

  • 去重:在集合中,所有元素必須相异
  • 無序:因為無序,所以不可索引
  • 可哈希:Python集合中的元素必須可以hash,即元素都可以使用內建函數hash
    • 目前學過不可hash的類型有:list、set、bytearray
  • 可迭代:set中雖然元素不一樣,但元素都可以迭代出來

增加

  • add(elem)

    • 增加一個元素到set中
    • 如果元素存在,什麼都不做
  • update(*others)
    • 合並其他元素到set集合中來
    • 參數others必須是可迭代對象
    • 就地修改
s = set()
s.add(1) s.update((1,2,3), [2,3,4])

删除

  • remove(elem)

    • 從set中移除一個元素
    • 元素不存在,拋出KeyError异常。為什麼是KeyError?
  • discard(elem)
    • 從set中移除一個元素
    • 元素不存在,什麼都不做
  • pop() -> item
    • 移除並返回任意的元素。為什麼是任意元素?
    • 空集返回KeyError异常
  • clear()
    • 移除所有元素
s = set(range(10))
s.remove(0)
#s.remove(11) # KeyError為什麼
s.discard(11) s.pop()
s.clear()

修改

集合類型沒有修改。因為元素唯一。如果元素能够加入到集合中,說明它和別的元素不一樣。

所謂修改,其實就是把當前元素改成一個完全不同的元素,就是删除加入新元素。

索引

非線性結構,不可索引。

成員運算符in

print(10 in [1, 2, 3])
print(10 in {1, 2, 3})

上面2句代碼,分別在列錶和集合中搜索元素。如果列錶和集合的元素都有100萬個,誰的效率高?

IPython魔術方法

IPython內置的特殊方法,使用%百分號開頭的

  • % 開頭是line magic
  • %% 開頭是 cell magic,notebook的cell
%timeit statement
-n 一個循環loop執行語句多少次
-r 循環執行多少次loop,取最好的結果
%%timeit setup_code
* code....
# 下面寫一行,列錶每次都要創建,這樣寫不好
%timeit (-1 in list(range(100)))
# 下面寫在一個cell中,寫在setup中,列錶創建一次
%%timeit l=list(range(1000000))
-1 in l

set和線性結構比較

結果說明,集合性能很好。為什麼?

  • 線性數據結構,搜索元素的時間複雜度是O(n),即隨著數據規模增加耗時增大
  • set、dict使用hash錶實現,內部使用hash值作為key,時間複雜度為O(1),查詢時間和數據規模無關,不會隨著數據規模增大而搜索性能下降。

遍曆

只要是容器,都可以遍曆元素。但是效率都是O(n)

可哈希

  • 數值型int、float、complex
  • 布爾型True、False
  • 字符串string、bytes
  • tuple
  • None
  • 以上都是不可變類型,稱為可哈希類型,hashable

set元素必須是可hash的。

集合概念

  • 全集

    • 所有元素的集合。例如實數集,所有實數組成的集合就是全集
  • 子集subset和超集superset
    • 一個集合A所有元素都在另一個集合B內,A是B的子集,B是A的超集
  • 真子集和真超集
    • A是B的子集,且A不等於B,A就是B的真子集,B是A的真超集
  • 並集:多個集合合並的結果
  • 交集:多個集合的公共部分
  • 差集:集合中除去和其他集合公共部分

並集

將兩個集合A和B的所有的元素合並到一起,組成的集合稱作集合A與集合B的並集

  • union(*others) 返回和多個集合合並後的新的集合
  • | 運算符重載,等同union
  • update(*others) 和多個集合合並,就地修改
  • |= 等同update

交集

集合A和B,由所有屬於A且屬於B的元素組成的集合

  • intersection(*others) 返回和多個集合的交集
  • & 等同intersection
  • intersection_update(*others) 獲取和多個集合的交集,並就地修改
  • &= 等同intersection_update

差集

集合A和B,由所有屬於A且不屬於B的元素組成的集合

  • difference(*others) 返回和多個集合的差集
  • - 等同difference
  • difference_update(*others) 獲取和多個集合的差集並就地修改
  • -= 等同difference_update

對稱交差

集合A和B,由所有不屬於A和B的交集元素組成的集合,記作(A-B)∪(B-A)

  • symmetric_differece(other) 返回和另一個集合的對稱差集
  • ^ 等同symmetric_differece
  • symmetric_differece_update(other) 獲取和另一個集合的對稱差集並就地修改
  • ^= 等同symmetric_differece_update

其它集合運算

  • issubset(other)、<= 判斷當前集合是否是另一個集合的子集
  • set1 < set2 判斷set1是否是set2的真子集
  • issuperset(other)、>= 判斷當前集合是否是other的超集
  • set1 > set2 判斷set1是否是set2的真超集
  • isdisjoint(other) 當前集合和另一個集合沒有交集,沒有交集,返回True

練習

  • 一個總任務列錶,存儲所有任務。一個已完成的任務列錶。找出為未完成的任務
業務中,任務ID一般不可以重複
所有任務ID放到一個set中,假設為ALL
所有已完成的任務ID放到一個set中,假設為COMPLETED,它是ALL的子集
ALL - COMPLETED => UNCOMPLETED

集合運算,用好了妙用無窮。

字典Dict

Dict即Dictionary,也稱為mapping。

Python中,字典由任意個元素構成的集合,每一個元素稱為Item,也稱為Entry。這個Item是由(key, value)組成的二元組。

字典是可變的、無序的、key不重複的key-value pairs鍵值對集合。

初始化

  • dict(**kwargs) 使用name=value對初始化一個字典

  • dict(iterable, **kwarg) 使用可迭代對象和name=value對構造字典,不過可迭代對象的元素必須是一個二元結構

  • dict(mapping, **kwarg) 使用一個字典構建另一個字典

字典的初始化方法都非常常用,都需要會用

d1 = {}
d2 = dict()
d3 = dict(a=100, b=200)
d4 = dict(d3) # 構造另外一個字典
d5 = dict(d4, a=300, c=400)
d6 = dict([('a', 100), ['b', 200], (1, 'abc')], b=300, c=400)
# 類方法dict.fromkeys(iterable, value)
d = dict.fromkeys(range(5))
d = dict.fromkeys(range(5), 0)

元素訪問

  • d[key]

    • 返回key對應的值value
    • key不存在拋出KeyError异常
  • get(key[, default])
    • 返回key對應的值value
    • key不存在返回缺省值,如果沒有設置缺省值就返回None
  • setdefault(key[, default])
    • 返回key對應的值value
    • key不存在,添加kv對,value設置為default,並返回default,如果default沒有設置,缺省為None

新增和修改

  • d[key] = value

    • 將key對應的值修改為value
    • key不存在添加新的kv對
  • update([other]) -> None
    • 使用另一個字典的kv對更新本字典
    • key不存在,就添加
    • key存在,覆蓋已經存在的key對應的值
    • 就地修改
d = {}
d['a'] = 1 d.update(red=1) d.update(['red', 2])
d.update({'red':3})

删除

  • pop(key[, default])

    • key存在,移除它,並返回它的value
    • key不存在,返回給定的default
    • default未設置,key不存在則拋出KeyError异常
  • popitem()
    • 移除並返回一個任意的鍵值對
    • 字典為empty,拋出KeyError异常
  • clear()
    • 清空字典

遍曆

1、遍曆Key

for k in d:
   print(k)
for k in d.keys():
   print(k)

2、遍曆Value

for v in d.values():
   print(v)
for k in d.keys():
   print(d[k])
   print(d.get(k))

3、遍曆Item

for item in d.items():
   print(item)
   print(item[0], item[1])
for k,v in d.items():
   print(k, v)
for k,_ in d.items():
   print(k)
for _,v in d.items():
   print(v)

Python3中,keys、values、items方法返回一個類似一個生成器的可迭代對象

  • Dictionary view對象,可以使用len()、iter()、in操作
  • 字典的entry的動態的視圖,字典變化,視圖將反映出這些變化
  • keys()返回一個類set對象,也就是可以看做一個set集合。如果values()都可以hash,那麼items()也可以看做是類set對象

Python2中,上面的方法會返回一個新的列錶,立即占據新的內存空間。所以Python2建議使用iterkeys、itervalues、iteritems版本,返回一個迭代器,而不是返回一個copy

遍曆與删除

# 錯誤的做法
d = dict(a=1, b=2, c=3)
for k,v in d.items():
   print(d.pop(k))
拋出RuntimeError: dictionary changed size during iteration

在使用keys、values、items方法遍曆的時候,不可以改變字典的size

while len(d):
   print(d.popitem())
while d:
   print(d.popitem())

上面的while循環雖然可以移除字典元素,但是很少使用,不如直接clear。

# for 循環正確删除
d = dict(a=1, b=2, c=3)
keys = []
for k,v in d.items():
keys.append(k)
for k in keys:
   d.pop(k)

集合set在遍曆中,也不能改變其長度。

key

字典的key和set的元素要求一致

  • set的元素可以就是看做key,set可以看做dict的簡化版
  • hashable 可哈希才可以作為key,可以使用hash()測試
  • 使用key訪問,就如同列錶使用index訪問一樣,時間複雜度都是O(1),這也是最好的訪問元素的方式
if __name__ == '__main__':
d = {
1: 0,
2.0: 3,
"abc": None,
('hello', 'world', 'python'): "string",
b'abc': '135'
}

有序性

字典元素是按照key的hash值無序存儲的。

但是,有時候我們卻需要一個有序的元素順序,Python 3.6之前,使用OrderedDict類可以做到,3.6開 始dict自身支持。到底Python對一個無序數據結構記錄了什麼順序?

# 3.5如下
C:\Python\Python353>python
Python 3.5.3 (v3.5.3:1880cb95a742, Jan 16 2017, 16:02:32) [MSC v.1900 64 bit
(AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> d = {'a':300, 'b':200, 'c':100, 'd':50}
>>> d
{'c': 100, 'a': 300, 'b': 200, 'd': 50}
>>> d
{'c': 100, 'a': 300, 'b': 200, 'd': 50}
>>> list(d.keys())
['c', 'a', 'b', 'd']
>>> exit()
C:\Python\Python353>python
Python 3.5.3 (v3.5.3:1880cb95a742, Jan 16 2017, 16:02:32) [MSC v.1900 64 bit
(AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> d = {'a':300, 'b':200, 'c':100, 'd':50}
>>> d
{'b': 200, 'c': 100, 'd': 50, 'a': 300}

Python 3.6之前,在不同的機器上,甚至同一個程序分別運行2次,都不能確定不同的key的先後順序。

# 3.6+錶現如下
C:\Python\python366>python
Python 3.6.6 (v3.6.6:4cf1f54eb7, Jun 27 2018, 03:37:03) [MSC v.1900 64 bit
(AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> d = {'c': 100, 'a': 300, 'b': 200, 'd': 50}
>>> d
{'c': 100, 'a': 300, 'b': 200, 'd': 50}
>>> exit()
C:\Python\python366>python
Python 3.6.6 (v3.6.6:4cf1f54eb7, Jun 27 2018, 03:37:03) [MSC v.1900 64 bit
(AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> d = {'c': 100, 'a': 300, 'b': 200, 'd': 50}
>>> d
{'c': 100, 'a': 300, 'b': 200, 'd': 50}
>>> d.keys()
dict_keys(['c', 'a', 'b', 'd'])

Python 3.6+,記錄了字典key的錄入順序,遍曆的時候,就是按照這個順序。

如果使用 d = {'a':300, 'b':200, 'c':100, 'd':50} ,就會造成以為字典按照key排序的錯覺。

目前,建議不要3.6+提供的這種字典特性,還是認為字典返回的是無序的,可以在Python不同版本中考慮使用OrderedDict類來保證這種錄入序。

04.python哈希錶的更多相關文章

  1. Python哈希錶的例子:dict、set

    dict(字典) Python內置了字典:dict的支持,dict全稱dictionary,在其他語言中也稱為map,使用鍵-值(key-value)存儲,具有極快的查找速度. 和list比較,dic ...

  2. Python哈希錶和解析式

    目錄 1. 封裝和解構 1.1 封裝 1.2 解構 2. 集合Set 2.1 初始化 2.2 增加 2.3 删除 2.4 遍曆 2.5 並集&交集&差集&對稱差集 3.字典 3 ...

  3. python數據結構與算法——哈希錶

    哈希錶 學習筆記 參考翻譯自:<複雜性思考> 及對應的online版本:http://greenteapress.com/complexity/html/thinkcomplexity00 ...

  4. 用python實現哈希錶

    哈哈,這是我第一篇博客園的博客.嘗試了一下用python實現的哈希錶,首先處理沖突的方法是開放地址法,沖突錶達式為Hi=(H(key)+1)mod m,m為錶長. #! /usr/bin/env py ...

  5. python數據結構之哈希錶

    哈希錶(Hash table) 眾所周知,HashMap是一個用於存儲Key-Value鍵值對的集合,每一個鍵值對也叫做Entry.這些個鍵值對(Entry)分散存儲在一個數組當中,這個數組就是Has ...

  6. 【Python算法】哈希存儲、哈希錶、散列錶原理

    哈希錶的定義: 哈希存儲的基本思想是以關鍵字Key為自變量,通過一定的函數關系(散列函數或哈希函數),計算出對應的函數值(哈希地址),以這個值作為數據元素的地址,並將數據元素存入到相應地址的存儲單元中 ...

  7. 使用python實現哈希錶、字典、集合

    哈希錶 哈希錶(Hash Table, 又稱為散列錶),是一種線性錶的存儲結構.哈希錶由一個直接尋址錶和一個哈希函數組成.哈希函數h(k)將元素關鍵字k作為自變量,返回元素的存儲下標. 簡單哈希函數: ...

  8. python code practice(二):KMP算法、二分搜索的實現、哈希錶

    1.替換空格 題目描述:請實現一個函數,將一個字符串中的每個空格替換成“%20”.例如,當字符串為We Are Happy.則經過替換之後的字符串為We%20Are%20Happy. 分析: 將長度為 ...

  9. Python 中的哈希錶

    Python 中的哈希錶:對字典的理解 有沒有想過,Python中的字典為什麼這麼高效穩定.原因是他是建立在hash錶上.了解Python中的hash錶有助於更好的理解Python,因為Pytho ...

  10. 數據結構與算法Python版 熟悉哈希錶,了解Python字典底層實現

    Hash Table 散列錶(hash table)也被稱為哈希錶,它是一種根據鍵(key)來存儲值(value)的特殊線性結構. 常用於迅速的無序單點查找,其查找速度可達到常數級別的O(1). 散列 ...

隨機推薦

  1. Informatica相同環境與不同環境的導入導出( Repository Name,Integration Service Name,Folder Name是否相同):

    Informatica相同環境與不同環境的導入導出( Repository Name,Integration Service Name,Folder Name是否相同): 1.repository N ...

  2. C#多線程學習筆記

    using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threa ...

  3. Android優化——UI優化(五) Listview 重用convertView

    1.重用convertView 我們對convertView添加判斷,如果存在我們就直接使用,否則初始化一個convertView的實例.(如下圖) 2.使用viewHolder 使用viewHold ...

  4. sqlite ef6 踩坑

    調試的時候配置寫如下,這樣寫是沒有問題的但是在實際環境中有問題,因為EF路徑找不到.會提示錯誤:The underlying provider failed on open <connectio ...

  5. 開發Nginx模塊Helloworld

    本文是對<深入理解Nginx>一書中的實例進行實戰時的記錄. 1模塊目錄結構 my_test_module/ ├── config └── ngx_http_mytest_module.c ...

  6. MySQL ERROR 1054(42S22)

    修改用戶的密碼,網上搜到的命令為如下 執行後報錯 ERROR 1054(42S22) Unknown column 'password' in ‘field list’ 錯誤的原因是 5.7版本下的m ...

  7. Win7 查看端口占用的進程,並根據進程id殺死進程。

    搞開發的經常會有一堆的工具要使用,而很多工具都需要開啟特定的端口,難免會出現端口沖突的場景,那在Win7 環境下如何排除端口被哪個進程占用了呢? 首先,通過 netstat -ano | findst ...

  8. 深入Session2

    一.分布式環境Session的處理方法 分布式環境下要保持會話跟踪最簡單的方式是只依靠客戶端Cookie保存,不過大多數情况下還需要用到Session,一般的處理方式如下: 1.Session複制 每 ...

  9. mysql 的安裝,密碼及修改 ,權限,基礎語句(增删改查)

    參考網址:https://www.cnblogs.com/majj/p/9160383.html    (安裝等) https://www.cnblogs.com/majj/p/9160421.htm ...

  10. Eclipse出現An error has occurred,See error log for more details的錯誤

    因為加入了Aptana組件所以一直報這個錯誤,用了cmd的方法依然不奏效,最後選擇 Window > perferences > General > Startup and Shut ...