今天看了哈希表原理，理解了个大概：
python 的 字典是基于哈希表实现的，之所以字典的存取操作的时间复杂度为O1也得益于哈希表。
我们知道，数组的时间复杂度为O1，是因为数组实现了以索引存取值，这样在存取数据的时候，只需要
将索引（内存地址）拿到，就能很快地将数据进行存取操作，一步到位。当然插入和删除因为要涉及全部元素
所以时间复杂度是另一个级别。
而字典，其实就是一个变相的数组。它将我们要存储的字符串先转化为 数字 索引，然后再存到列表里。
这里 可以想象，由于同样的字符串转化为数字索引的时候（如果是用同一种算法），可定会发生重复，即
碰撞。这里不写解决碰撞的方法，本例中 思路是将每个字符串存进表的时候，挂上一个独一无二的id。
talk is cheap，代码实现如下：
import random
import time
class Hastable(object):
def __init__(self):
self.table_size = 100007
self.table = [0] * self.table_size
def add(self, key, value):
index = 1
f = 1
for s in key:
index += ord(s) * f
f *= 10
index = index % self.table_size
data = [key, value]
if self.table[index] == 0:
self.table[index] = [data]
else:
self.table[index].append(data)
def get(self, key, defult=None):
index = 1
f = 1
for k in key:
index += ord(k) * f
f *= 10
index = index % self.table_size
if isinstance(self.table[index], list):
for ls in self.table[index]:
if ls[0] == key:
return ls[1]
else:
return defult
# -----------------以下为测试时间-----------
ls = []
def ran():
seed = 'abcdefghijklmnopqrstuvwxyz'
s = ''
for i in range(5):
random_index = random.randint(0, len(seed) - 1)
s += seed[random_index]
ls.append(s)
def ye(n):
i = 0
while i < n:
ran()
i += 1
def test():
import uuid
t1 = time.time()
print('list add start', t1)
ye(500000)
t2 = time.time()
print('list add end', t2)
print('total time', t2 - t1)
print("=====================")
t3 = time.time()
print('Hastable add start', t3)
ht = Hastable()
for key in ls:
value = uuid.uuid4()
# print('value', value)
ht.add(key, value)
t4 = time.time()
print('Hastable add total', t4 - t3)
print("=====================")
t5 = time.time()
print('Hastable get start', t5)
for key in ls:
v = ht.get(key)
t6 = time.time()
print('Hastable get total', t6 - t5)
print("=====================")
t7 = time.time()
print('list get start', t7)
for i in range(len(ls)):
ls.__getitem__(i)
t8 = time.time()
print('list get total', t8 - t7)
print('all time', t8 - t1)
if __name__ == '__main__':
test()
输出如下：
list add start 1527833095.2639012
list add end 1527833102.5443177
total time 7.280416488647461
=====================
Hastable add start 1527833102.5443177
Hastable add total 6.015344142913818
=====================
Hastable get start 1527833108.5596619
Hastable get total 1.8111035823822021
=====================
list get start 1527833110.3707654
list get total 0.07000398635864258
all time 15.176868200302124
[Finished in 15.7s]
