python中的哈希表实现

我想在python中实现哈希表。由于哈希的基本思想是将值存储在索引i中，其中i = hash_function（key），我需要能够索引列表/数组来存储值。但由于python中的列表大小通过.append（）扩展，因此hashList [i]语句会导致“列表分配索引超出范围”。python中的哈希表实现

有没有扭曲使用固定大小的列表和索引它通常？或者我应该使用一个ctype数组？

下面的代码可能看起来怎么样：

class Hash(): 
    length = 1000 
    array = [] 

    def __setitem__(self, key, value): 
     sum = 0 
     if key != None: 
      for letter in key: 
       sum = sum + ord(letter) 
     self.array[sum % self.length] = self.length

来源

2013-11-27 Shimaa

我认为这是“学院派” - 蟒蛇已经有一个美好的内置哈希表称为'dict' – mgilson

创建列表以'listSize'许多'None's开始。那么你可以考虑一个带有'None'的索引是一个空的哈希桶 – inspectorG4dget

@mgilson：根据用例，OP也可以考虑使用'set' – inspectorG4dget

class HashTable(): 

    def __init__(self): 
     self.size = 1000 
     self.table = [None] * self.size 

    def add(self, item): 
     hashcode = self.hash(item) 
     if hashcode >= self.size: 
      # Resize the table. 
      self.size *= 2 
      # etc. 
     else: 
      self.table[hashcode] = item 

    def hash(self, item): 
     # Your implementation of a hash function.

来源

2013-11-27 21:51:21 sdasdadas

该哈希表实现无法处理冲突。 – user4815162342

确实“[None] * self.size”消耗O（大小）时间？ – Shimaa

@ user1203631但是'add'功能还有很多空间。 :) – sdasdadas

是否有使用列表具有固定的大小和索引它通常是一个扭曲？

是，初始化数组即

for i in range(0,1000): 
    array.append(None)

然后你就可以继续前进，在0-9999

之间的任何指标设置你的价值观 -

我将使用一个命令类型数组？

Python lists are arrays

来源

2013-11-27 21:50:21 JoeC

如果你打算预定义你的数组，'[None] * 1000'应该快很多。 –

由于@mgilson指出，该字典是内置的哈希表蟒蛇，所以这个答案假定你这样做是为唯一的学术原因。

下面是创建在python一个固定大小的列表填充无值的一种方法：

import itertools 

hashSize = 100 
myHashList = list(itertools.repeat(None, hashSize))

约当你在哈希表耗尽空间做什么的详细信息，请参阅Wikipedia: Hash Table - Dynamic resizing。

来源

2013-11-27 21:50:42 Hans

python中的哈希表实现

回答

相关问题