| 24 | # 冲突解决:分离链--冲突位置排成一个链; linear probing发生冲突去下一个位置 |
| 25 | |
| 26 | class HashTable: |
| 27 | def __init__(self): |
| 28 | self.size = 11 |
| 29 | self.slots = [None] * self.size |
| 30 | self.data = [None] * self.size |
| 31 | |
| 32 | def put(self, key, data): |
| 33 | hashvalue = self.hashfunction(key, self.size) |
| 34 | |
| 35 | if self.slots[hashvalue] == None: |
| 36 | self.slots[hashvalue] = key |
| 37 | self.data[hashvalue] = data |
| 38 | else: |
| 39 | if self.slots[hashvalue] == key: |
| 40 | self.data[hashvalue] = data # 替换相同索引对应的项目 |
| 41 | else: |
| 42 | if None not in self.slots and key not in self.slots: |
| 43 | # 判断hash是否已经满了, 必须添加key not in self.slots, 否则修改已有hash值会直接返回-1 |
| 44 | print('sorry, there is not enough slots for you!') |
| 45 | return -1 |
| 46 | nextslot = self.rehash(hashvalue, len(self.slots)) |
| 47 | while self.slots[nextslot] != None and self.slots[nextslot] != key: |
| 48 | nextslot = self.rehash(nextslot, len(self.slots)) |
| 49 | |
| 50 | if self.slots[nextslot] == None: |
| 51 | self.slots[nextslot] = key |
| 52 | self.data[nextslot] = data |
| 53 | else: |
| 54 | self.data[nextslot] = data |
| 55 | |
| 56 | def hashfunction(self, key, size): |
| 57 | return key%size |
| 58 | |
| 59 | def rehash(self, oldhash, size): |
| 60 | return (oldhash+1)%size |
| 61 | |
| 62 | def get(self, key): |
| 63 | startslot = self.hashfunction(key, len(self.slots)) |
| 64 | |
| 65 | data = None |
| 66 | stop = False |
| 67 | found = False |
| 68 | position = startslot |
| 69 | while self.slots[position] != None and not found and not stop: |
| 70 | if self.slots[position] == key: |
| 71 | found = True |
| 72 | data = self.data[position] |
| 73 | else: |
| 74 | position = self.rehash(position, len(self.slots)) |
| 75 | if position == startslot: |
| 76 | stop = True |
| 77 | return data |
| 78 | |
| 79 | def __getitem__(self, key): |
| 80 | return self.get(key) |
| 81 | |
| 82 | def __setitem__(self, key, data): |
| 83 | self.put(key, data) |