AlgorithmsByPython/Hash.py at master · DouTong/AlgorithmsByPython · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
# 用Python实现hash表
# hash的查找操作时间复杂度O(1)
# hash每个位置被称为slot槽。可以使用list实现hash,每个slot对应一个key,存放元素

# 按照正常的字母在ASCII中的顺序mod tablesize构造hash
defhash(astring, tablesize):
sum=0
forposinastring:
sum=sum+ord(pos)

returnsum%tablesize

print(hash('cat', 11)) # cat在hash中的位置,hash table长度11

# 改进hash, 让每一位的字母乘以该字母在字串中的位置然后mod
defhash2(astring, tablesize):
sum=0
forposinrange(len(astring)):
sum+= (pos+1) *ord(astring[pos])
returnsum%tablesize

print(hash2('cat', 11))

# 冲突解决:分离链--冲突位置排成一个链; linear probing发生冲突去下一个位置

classHashTable:
def__init__(self):
self.size=11
self.slots= [None] *self.size
self.data= [None] *self.size

defput(self, key, data):
hashvalue=self.hashfunction(key, self.size)

ifself.slots[hashvalue] ==None:
self.slots[hashvalue] =key
self.data[hashvalue] =data
else:
ifself.slots[hashvalue] ==key:
self.data[hashvalue] =data# 替换相同索引对应的项目
else:
ifNonenotinself.slotsandkeynotinself.slots:
# 判断hash是否已经满了, 必须添加key not in self.slots, 否则修改已有hash值会直接返回-1
print('sorry, there is not enough slots for you!')
return-1
nextslot=self.rehash(hashvalue, len(self.slots))
whileself.slots[nextslot] !=Noneandself.slots[nextslot] !=key:
nextslot=self.rehash(nextslot, len(self.slots))

ifself.slots[nextslot] ==None:
self.slots[nextslot] =key
self.data[nextslot] =data
else:
self.data[nextslot] =data

defhashfunction(self, key, size):
returnkey%size

defrehash(self, oldhash, size):
return (oldhash+1)%size

defget(self, key):
startslot=self.hashfunction(key, len(self.slots))

data=None
stop=False
found=False
position=startslot
whileself.slots[position] !=Noneandnotfoundandnotstop:
ifself.slots[position] ==key:
found=True
data=self.data[position]
else:
position=self.rehash(position, len(self.slots))
ifposition==startslot:
stop=True
returndata

def__getitem__(self, key):
returnself.get(key)

def__setitem__(self, key, data):
self.put(key, data)

H=HashTable()
H[54] ='cat'
H[26] ="dog"
H[93] ="lion"
H[17] ="tiger"
H[77] ="bird"
H[31] ="cow"
H[44] ="goat"
H[55] ="pig"
H[20] ="chicken"
print(H[20])
print(H.slots)
print(H.data)
print(H[99])
H[21] ="elephant"
H[22] ="sheep"
H[23] ="fish"
print(H.data)
H[20] ='monkey'
print(H.data)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
# 用Python实现hash表
# hash的查找操作时间复杂度O(1)
# hash每个位置被称为slot槽。可以使用list实现hash,每个slot对应一个key,存放元素

# 按照正常的字母在ASCII中的顺序mod tablesize构造hash
defhash(astring, tablesize):
sum=0
forposinastring:
sum=sum+ord(pos)

returnsum%tablesize

print(hash('cat', 11)) # cat在hash中的位置,hash table长度11

# 改进hash, 让每一位的字母乘以该字母在字串中的位置然后mod
defhash2(astring, tablesize):
sum=0
forposinrange(len(astring)):
sum+= (pos+1) *ord(astring[pos])
returnsum%tablesize

print(hash2('cat', 11))

# 冲突解决:分离链--冲突位置排成一个链; linear probing发生冲突去下一个位置

classHashTable:
def__init__(self):
self.size=11
self.slots= [None] *self.size
self.data= [None] *self.size

defput(self, key, data):
hashvalue=self.hashfunction(key, self.size)

ifself.slots[hashvalue] ==None:
self.slots[hashvalue] =key
self.data[hashvalue] =data
else:
ifself.slots[hashvalue] ==key:
self.data[hashvalue] =data# 替换相同索引对应的项目
else:
ifNonenotinself.slotsandkeynotinself.slots:
# 判断hash是否已经满了, 必须添加key not in self.slots, 否则修改已有hash值会直接返回-1
print('sorry, there is not enough slots for you!')
return-1
nextslot=self.rehash(hashvalue, len(self.slots))
whileself.slots[nextslot] !=Noneandself.slots[nextslot] !=key:
nextslot=self.rehash(nextslot, len(self.slots))

ifself.slots[nextslot] ==None:
self.slots[nextslot] =key
self.data[nextslot] =data
else:
self.data[nextslot] =data

defhashfunction(self, key, size):
returnkey%size

defrehash(self, oldhash, size):
return (oldhash+1)%size

defget(self, key):
startslot=self.hashfunction(key, len(self.slots))

data=None
stop=False
found=False
position=startslot
whileself.slots[position] !=Noneandnotfoundandnotstop:
ifself.slots[position] ==key:
found=True
data=self.data[position]
else:
position=self.rehash(position, len(self.slots))
ifposition==startslot:
stop=True
returndata

def__getitem__(self, key):
returnself.get(key)

def__setitem__(self, key, data):
self.put(key, data)

H=HashTable()
H[54] ='cat'
H[26] ="dog"
H[93] ="lion"
H[17] ="tiger"
H[77] ="bird"
H[31] ="cow"
H[44] ="goat"
H[55] ="pig"
H[20] ="chicken"
print(H[20])
print(H.slots)
print(H.data)
print(H[99])
H[21] ="elephant"
H[22] ="sheep"
H[23] ="fish"
print(H.data)
H[20] ='monkey'
print(H.data)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
# 用Python实现hash表
# hash的查找操作时间复杂度O(1)
# hash每个位置被称为slot槽。可以使用list实现hash,每个slot对应一个key,存放元素

# 按照正常的字母在ASCII中的顺序mod tablesize构造hash
defhash(astring, tablesize):
sum=0
forposinastring:
sum=sum+ord(pos)

returnsum%tablesize

print(hash('cat', 11)) # cat在hash中的位置,hash table长度11

# 改进hash, 让每一位的字母乘以该字母在字串中的位置然后mod
defhash2(astring, tablesize):
sum=0
forposinrange(len(astring)):
sum+= (pos+1) *ord(astring[pos])
returnsum%tablesize

print(hash2('cat', 11))

# 冲突解决:分离链--冲突位置排成一个链; linear probing发生冲突去下一个位置

classHashTable:
def__init__(self):
self.size=11
self.slots= [None] *self.size
self.data= [None] *self.size

defput(self, key, data):
hashvalue=self.hashfunction(key, self.size)

ifself.slots[hashvalue] ==None:
self.slots[hashvalue] =key
self.data[hashvalue] =data
else:
ifself.slots[hashvalue] ==key:
self.data[hashvalue] =data# 替换相同索引对应的项目
else:
ifNonenotinself.slotsandkeynotinself.slots:
# 判断hash是否已经满了, 必须添加key not in self.slots, 否则修改已有hash值会直接返回-1
print('sorry, there is not enough slots for you!')
return-1
nextslot=self.rehash(hashvalue, len(self.slots))
whileself.slots[nextslot] !=Noneandself.slots[nextslot] !=key:
nextslot=self.rehash(nextslot, len(self.slots))

ifself.slots[nextslot] ==None:
self.slots[nextslot] =key
self.data[nextslot] =data
else:
self.data[nextslot] =data

defhashfunction(self, key, size):
returnkey%size

defrehash(self, oldhash, size):
return (oldhash+1)%size

defget(self, key):
startslot=self.hashfunction(key, len(self.slots))

data=None
stop=False
found=False
position=startslot
whileself.slots[position] !=Noneandnotfoundandnotstop:
ifself.slots[position] ==key:
found=True
data=self.data[position]
else:
position=self.rehash(position, len(self.slots))
ifposition==startslot:
stop=True
returndata

def__getitem__(self, key):
returnself.get(key)

def__setitem__(self, key, data):
self.put(key, data)

H=HashTable()
H[54] ='cat'
H[26] ="dog"
H[93] ="lion"
H[17] ="tiger"
H[77] ="bird"
H[31] ="cow"
H[44] ="goat"
H[55] ="pig"
H[20] ="chicken"
print(H[20])
print(H.slots)
print(H.data)
print(H[99])
H[21] ="elephant"
H[22] ="sheep"
H[23] ="fish"
print(H.data)
H[20] ='monkey'
print(H.data)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
# 用Python实现hash表
# hash的查找操作时间复杂度O(1)
# hash每个位置被称为slot槽。可以使用list实现hash,每个slot对应一个key,存放元素

# 按照正常的字母在ASCII中的顺序mod tablesize构造hash
defhash(astring, tablesize):
sum=0
forposinastring:
sum=sum+ord(pos)

returnsum%tablesize

print(hash('cat', 11)) # cat在hash中的位置,hash table长度11

# 改进hash, 让每一位的字母乘以该字母在字串中的位置然后mod
defhash2(astring, tablesize):
sum=0
forposinrange(len(astring)):
sum+= (pos+1) *ord(astring[pos])
returnsum%tablesize

print(hash2('cat', 11))

# 冲突解决:分离链--冲突位置排成一个链; linear probing发生冲突去下一个位置

classHashTable:
def__init__(self):
self.size=11
self.slots= [None] *self.size
self.data= [None] *self.size

defput(self, key, data):
hashvalue=self.hashfunction(key, self.size)

ifself.slots[hashvalue] ==None:
self.slots[hashvalue] =key
self.data[hashvalue] =data
else:
ifself.slots[hashvalue] ==key:
self.data[hashvalue] =data# 替换相同索引对应的项目
else:
ifNonenotinself.slotsandkeynotinself.slots:
# 判断hash是否已经满了, 必须添加key not in self.slots, 否则修改已有hash值会直接返回-1
print('sorry, there is not enough slots for you!')
return-1
nextslot=self.rehash(hashvalue, len(self.slots))
whileself.slots[nextslot] !=Noneandself.slots[nextslot] !=key:
nextslot=self.rehash(nextslot, len(self.slots))

ifself.slots[nextslot] ==None:
self.slots[nextslot] =key
self.data[nextslot] =data
else:
self.data[nextslot] =data

defhashfunction(self, key, size):
returnkey%size

defrehash(self, oldhash, size):
return (oldhash+1)%size

defget(self, key):
startslot=self.hashfunction(key, len(self.slots))

data=None
stop=False
found=False
position=startslot
whileself.slots[position] !=Noneandnotfoundandnotstop:
ifself.slots[position] ==key:
found=True
data=self.data[position]
else:
position=self.rehash(position, len(self.slots))
ifposition==startslot:
stop=True
returndata

def__getitem__(self, key):
returnself.get(key)

def__setitem__(self, key, data):
self.put(key, data)

H=HashTable()
H[54] ='cat'
H[26] ="dog"
H[93] ="lion"
H[17] ="tiger"
H[77] ="bird"
H[31] ="cow"
H[44] ="goat"
H[55] ="pig"
H[20] ="chicken"
print(H[20])
print(H.slots)
print(H.data)
print(H[99])
H[21] ="elephant"
H[22] ="sheep"
H[23] ="fish"
print(H.data)
H[20] ='monkey'
print(H.data)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
# 用Python实现hash表
# hash的查找操作时间复杂度O(1)
# hash每个位置被称为slot槽。可以使用list实现hash,每个slot对应一个key,存放元素

# 按照正常的字母在ASCII中的顺序mod tablesize构造hash
defhash(astring, tablesize):
sum=0
forposinastring:
sum=sum+ord(pos)

returnsum%tablesize

print(hash('cat', 11)) # cat在hash中的位置,hash table长度11

# 改进hash, 让每一位的字母乘以该字母在字串中的位置然后mod
defhash2(astring, tablesize):
sum=0
forposinrange(len(astring)):
sum+= (pos+1) *ord(astring[pos])
returnsum%tablesize

print(hash2('cat', 11))

# 冲突解决:分离链--冲突位置排成一个链; linear probing发生冲突去下一个位置

classHashTable:
def__init__(self):
self.size=11
self.slots= [None] *self.size
self.data= [None] *self.size

defput(self, key, data):
hashvalue=self.hashfunction(key, self.size)

ifself.slots[hashvalue] ==None:
self.slots[hashvalue] =key
self.data[hashvalue] =data
else:
ifself.slots[hashvalue] ==key:
self.data[hashvalue] =data# 替换相同索引对应的项目
else:
ifNonenotinself.slotsandkeynotinself.slots:
# 判断hash是否已经满了, 必须添加key not in self.slots, 否则修改已有hash值会直接返回-1
print('sorry, there is not enough slots for you!')
return-1
nextslot=self.rehash(hashvalue, len(self.slots))
whileself.slots[nextslot] !=Noneandself.slots[nextslot] !=key:
nextslot=self.rehash(nextslot, len(self.slots))

ifself.slots[nextslot] ==None:
self.slots[nextslot] =key
self.data[nextslot] =data
else:
self.data[nextslot] =data

defhashfunction(self, key, size):
returnkey%size

defrehash(self, oldhash, size):
return (oldhash+1)%size

defget(self, key):
startslot=self.hashfunction(key, len(self.slots))

data=None
stop=False
found=False
position=startslot
whileself.slots[position] !=Noneandnotfoundandnotstop:
ifself.slots[position] ==key:
found=True
data=self.data[position]
else:
position=self.rehash(position, len(self.slots))
ifposition==startslot:
stop=True
returndata

def__getitem__(self, key):
returnself.get(key)

def__setitem__(self, key, data):
self.put(key, data)

H=HashTable()
H[54] ='cat'
H[26] ="dog"
H[93] ="lion"
H[17] ="tiger"
H[77] ="bird"
H[31] ="cow"
H[44] ="goat"
H[55] ="pig"
H[20] ="chicken"
print(H[20])
print(H.slots)
print(H.data)
print(H[99])
H[21] ="elephant"
H[22] ="sheep"
H[23] ="fish"
print(H.data)
H[20] ='monkey'
print(H.data)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
# 用Python实现hash表
# hash的查找操作时间复杂度O(1)
# hash每个位置被称为slot槽。可以使用list实现hash,每个slot对应一个key,存放元素

# 按照正常的字母在ASCII中的顺序mod tablesize构造hash
defhash(astring, tablesize):
sum=0
forposinastring:
sum=sum+ord(pos)

returnsum%tablesize

print(hash('cat', 11)) # cat在hash中的位置,hash table长度11

# 改进hash, 让每一位的字母乘以该字母在字串中的位置然后mod
defhash2(astring, tablesize):
sum=0
forposinrange(len(astring)):
sum+= (pos+1) *ord(astring[pos])
returnsum%tablesize

print(hash2('cat', 11))

# 冲突解决:分离链--冲突位置排成一个链; linear probing发生冲突去下一个位置

classHashTable:
def__init__(self):
self.size=11
self.slots= [None] *self.size
self.data= [None] *self.size

defput(self, key, data):
hashvalue=self.hashfunction(key, self.size)

ifself.slots[hashvalue] ==None:
self.slots[hashvalue] =key
self.data[hashvalue] =data
else:
ifself.slots[hashvalue] ==key:
self.data[hashvalue] =data# 替换相同索引对应的项目
else:
ifNonenotinself.slotsandkeynotinself.slots:
# 判断hash是否已经满了, 必须添加key not in self.slots, 否则修改已有hash值会直接返回-1
print('sorry, there is not enough slots for you!')
return-1
nextslot=self.rehash(hashvalue, len(self.slots))
whileself.slots[nextslot] !=Noneandself.slots[nextslot] !=key:
nextslot=self.rehash(nextslot, len(self.slots))

ifself.slots[nextslot] ==None:
self.slots[nextslot] =key
self.data[nextslot] =data
else:
self.data[nextslot] =data

defhashfunction(self, key, size):
returnkey%size

defrehash(self, oldhash, size):
return (oldhash+1)%size

defget(self, key):
startslot=self.hashfunction(key, len(self.slots))

data=None
stop=False
found=False
position=startslot
whileself.slots[position] !=Noneandnotfoundandnotstop:
ifself.slots[position] ==key:
found=True
data=self.data[position]
else:
position=self.rehash(position, len(self.slots))
ifposition==startslot:
stop=True
returndata

def__getitem__(self, key):
returnself.get(key)

def__setitem__(self, key, data):
self.put(key, data)

H=HashTable()
H[54] ='cat'
H[26] ="dog"
H[93] ="lion"
H[17] ="tiger"
H[77] ="bird"
H[31] ="cow"
H[44] ="goat"
H[55] ="pig"
H[20] ="chicken"
print(H[20])
print(H.slots)
print(H.data)
print(H[99])
H[21] ="elephant"
H[22] ="sheep"
H[23] ="fish"
print(H.data)
H[20] ='monkey'
print(H.data)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
# 用Python实现hash表
# hash的查找操作时间复杂度O(1)
# hash每个位置被称为slot槽。可以使用list实现hash,每个slot对应一个key,存放元素

# 按照正常的字母在ASCII中的顺序mod tablesize构造hash
defhash(astring, tablesize):
sum=0
forposinastring:
sum=sum+ord(pos)

returnsum%tablesize

print(hash('cat', 11)) # cat在hash中的位置,hash table长度11

# 改进hash, 让每一位的字母乘以该字母在字串中的位置然后mod
defhash2(astring, tablesize):
sum=0
forposinrange(len(astring)):
sum+= (pos+1) *ord(astring[pos])
returnsum%tablesize

print(hash2('cat', 11))

# 冲突解决:分离链--冲突位置排成一个链; linear probing发生冲突去下一个位置

classHashTable:
def__init__(self):
self.size=11
self.slots= [None] *self.size
self.data= [None] *self.size

defput(self, key, data):
hashvalue=self.hashfunction(key, self.size)

ifself.slots[hashvalue] ==None:
self.slots[hashvalue] =key
self.data[hashvalue] =data
else:
ifself.slots[hashvalue] ==key:
self.data[hashvalue] =data# 替换相同索引对应的项目
else:
ifNonenotinself.slotsandkeynotinself.slots:
# 判断hash是否已经满了, 必须添加key not in self.slots, 否则修改已有hash值会直接返回-1
print('sorry, there is not enough slots for you!')
return-1
nextslot=self.rehash(hashvalue, len(self.slots))
whileself.slots[nextslot] !=Noneandself.slots[nextslot] !=key:
nextslot=self.rehash(nextslot, len(self.slots))

ifself.slots[nextslot] ==None:
self.slots[nextslot] =key
self.data[nextslot] =data
else:
self.data[nextslot] =data

defhashfunction(self, key, size):
returnkey%size

defrehash(self, oldhash, size):
return (oldhash+1)%size

defget(self, key):
startslot=self.hashfunction(key, len(self.slots))

data=None
stop=False
found=False
position=startslot
whileself.slots[position] !=Noneandnotfoundandnotstop:
ifself.slots[position] ==key:
found=True
data=self.data[position]
else:
position=self.rehash(position, len(self.slots))
ifposition==startslot:
stop=True
returndata

def__getitem__(self, key):
returnself.get(key)

def__setitem__(self, key, data):
self.put(key, data)

H=HashTable()
H[54] ='cat'
H[26] ="dog"
H[93] ="lion"
H[17] ="tiger"
H[77] ="bird"
H[31] ="cow"
H[44] ="goat"
H[55] ="pig"
H[20] ="chicken"
print(H[20])
print(H.slots)
print(H.data)
print(H[99])
H[21] ="elephant"
H[22] ="sheep"
H[23] ="fish"
print(H.data)
H[20] ='monkey'
print(H.data)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
# 用Python实现hash表
# hash的查找操作时间复杂度O(1)
# hash每个位置被称为slot槽。可以使用list实现hash,每个slot对应一个key,存放元素

# 按照正常的字母在ASCII中的顺序mod tablesize构造hash
defhash(astring, tablesize):
sum=0
forposinastring:
sum=sum+ord(pos)

returnsum%tablesize

print(hash('cat', 11)) # cat在hash中的位置,hash table长度11

# 改进hash, 让每一位的字母乘以该字母在字串中的位置然后mod
defhash2(astring, tablesize):
sum=0
forposinrange(len(astring)):
sum+= (pos+1) *ord(astring[pos])
returnsum%tablesize

print(hash2('cat', 11))

# 冲突解决:分离链--冲突位置排成一个链; linear probing发生冲突去下一个位置

classHashTable:
def__init__(self):
self.size=11
self.slots= [None] *self.size
self.data= [None] *self.size

defput(self, key, data):
hashvalue=self.hashfunction(key, self.size)

ifself.slots[hashvalue] ==None:
self.slots[hashvalue] =key
self.data[hashvalue] =data
else:
ifself.slots[hashvalue] ==key:
self.data[hashvalue] =data# 替换相同索引对应的项目
else:
ifNonenotinself.slotsandkeynotinself.slots:
# 判断hash是否已经满了, 必须添加key not in self.slots, 否则修改已有hash值会直接返回-1
print('sorry, there is not enough slots for you!')
return-1
nextslot=self.rehash(hashvalue, len(self.slots))
whileself.slots[nextslot] !=Noneandself.slots[nextslot] !=key:
nextslot=self.rehash(nextslot, len(self.slots))

ifself.slots[nextslot] ==None:
self.slots[nextslot] =key
self.data[nextslot] =data
else:
self.data[nextslot] =data

defhashfunction(self, key, size):
returnkey%size

defrehash(self, oldhash, size):
return (oldhash+1)%size

defget(self, key):
startslot=self.hashfunction(key, len(self.slots))

data=None
stop=False
found=False
position=startslot
whileself.slots[position] !=Noneandnotfoundandnotstop:
ifself.slots[position] ==key:
found=True
data=self.data[position]
else:
position=self.rehash(position, len(self.slots))
ifposition==startslot:
stop=True
returndata

def__getitem__(self, key):
returnself.get(key)

def__setitem__(self, key, data):
self.put(key, data)

H=HashTable()
H[54] ='cat'
H[26] ="dog"
H[93] ="lion"
H[17] ="tiger"
H[77] ="bird"
H[31] ="cow"
H[44] ="goat"
H[55] ="pig"
H[20] ="chicken"
print(H[20])
print(H.slots)
print(H.data)
print(H[99])
H[21] ="elephant"
H[22] ="sheep"
H[23] ="fish"
print(H.data)
H[20] ='monkey'
print(H.data)