Python Hash及常见操作

本文阅读 1 分钟
首页 Python笔记 正文
  1. # 用Python实现hash表
  2. # hash的查找操作时间复杂度O(1)
  3. # hash每个位置被称为slot槽。可以使用list实现hash,每个slot对应一个key,存放元素
  4. # 按照正常的字母在ASCII中的顺序mod tablesize构造hash
  5. def hash(astring, tablesize):
  6. sum = 0
  7. for pos in astring:
  8. sum = sum + ord(pos)
  9. return sum%tablesize
  10. print(hash('cat', 11)) # cat在hash中的位置,hash table长度11
  11. # 改进hash, 让每一位的字母乘以该字母在字串中的位置然后mod
  12. def hash2(astring, tablesize):
  13. sum = 0
  14. for pos in range(len(astring)):
  15. sum += (pos+1) * ord(astring[pos])
  16. return sum%tablesize
  17. print(hash2('cat', 11))
  18. # 冲突解决:分离链--冲突位置排成一个链; linear probing发生冲突去下一个位置
  19. class HashTable:
  20. def __init__(self):
  21. self.size = 11
  22. self.slots = [None] * self.size
  23. self.data = [None] * self.size
  24. def put(self, key, data):
  25. hashvalue = self.hashfunction(key, self.size)
  26. if self.slots[hashvalue] == None:
  27. self.slots[hashvalue] = key
  28. self.data[hashvalue] = data
  29. else:
  30. if self.slots[hashvalue] == key:
  31. self.data[hashvalue] = data # 替换相同索引对应的项目
  32. else:
  33. if None not in self.slots and key not in self.slots:
  34. # 判断hash是否已经满了, 必须添加key not in self.slots, 否则修改已有hash值会直接返回-1
  35. print('sorry, there is not enough slots for you!')
  36. return -1
  37. nextslot = self.rehash(hashvalue, len(self.slots))
  38. while self.slots[nextslot] != None and self.slots[nextslot] != key:
  39. nextslot = self.rehash(nextslot, len(self.slots))
  40. if self.slots[nextslot] == None:
  41. self.slots[nextslot] = key
  42. self.data[nextslot] = data
  43. else:
  44. self.data[nextslot] = data
  45. def hashfunction(self, key, size):
  46. return key%size
  47. def rehash(self, oldhash, size):
  48. return (oldhash+1)%size
  49. def get(self, key):
  50. startslot = self.hashfunction(key, len(self.slots))
  51. data = None
  52. stop = False
  53. found = False
  54. position = startslot
  55. while self.slots[position] != None and not found and not stop:
  56. if self.slots[position] == key:
  57. found = True
  58. data = self.data[position]
  59. else:
  60. position = self.rehash(position, len(self.slots))
  61. if position == startslot:
  62. stop = True
  63. return data
  64. def __getitem__(self, key):
  65. return self.get(key)
  66. def __setitem__(self, key, data):
  67. self.put(key, data)
  68. H = HashTable()
  69. H[54] = 'cat'
  70. H[26] = "dog"
  71. H[93] = "lion"
  72. H[17] = "tiger"
  73. H[77] = "bird"
  74. H[31] = "cow"
  75. H[44] = "goat"
  76. H[55] = "pig"
  77. H[20] = "chicken"
  78. print(H[20])
  79. print(H.slots)
  80. print(H.data)
  81. print(H[99])
  82. H[21] = "elephant"
  83. H[22] = "sheep"
  84. H[23] = "fish"
  85. print(H.data)
  86. H[20] = 'monkey'
  87. print(H.data)
解压密码: detechn或detechn.com

免责声明

本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。

本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。

本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。

Python几个小的动态规划问题
« 上一篇 01-21
Python插入排序
下一篇 » 01-21

发表评论