我们为什么需要了解dict和set的实现原理呢？因为只有了解了其背后的实现原理，我们才能更好的的知道什么情况下使用dict以及set，这一点很重要，结合实际的情况使用不同的数据结构可能会产生很大的区别。

先通过一段测试代码了解一下它们性能之间的区别：

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
from random import randint


def load_list_data(total_nums, target_nums):
    """
    从文件中读取数据，以list的方式返回
    :param total_nums: 读取的数量
    :param target_nums: 需要查询的数据的数量
    """
    all_data = []
    target_data = []
    file_name = "./test.txt"    # test.txt是包含成千上万的字符的文件，自己可随意设置
    with open(file_name, encoding="utf8", mode="r") as f_open:
        for count, line in enumerate(f_open):
            if count < total_nums:
                all_data.append(line)
            else:
                break

    for x in range(target_nums):
        random_index = randint(0, total_nums)
        if all_data[random_index] not in target_data:
            target_data.append(all_data[random_index])
            if len(target_data) == target_nums:
                break

    return all_data, target_data


def load_dict_data(total_nums, target_nums):
    """
    从文件中读取数据，以dict的方式返回
    :param total_nums: 读取的数量
    :param target_nums: 需要查询的数据的数量
    """
    all_data = {}
    target_data = []
    file_name = "./test.txt"
    with open(file_name, encoding="utf8", mode="r") as f_open:
        for count, line in enumerate(f_open):
            if count < total_nums:
                all_data[line] = 0
            else:
                break
    all_data_list = list(all_data)
    for x in range(target_nums):
        random_index = randint(0, total_nums-1)
        if all_data_list[random_index] not in target_data:
            target_data.append(all_data_list[random_index])
            if len(target_data) == target_nums:
                break

    return all_data, target_data


def find_test(all_data, target_data):
    # 测试运行时间
    test_times = 100
    total_times = 0
    import time
    for i in range(test_times):
        find = 0
        start_time = time.time()
        for data in target_data:
            if data in all_data:
                find += 1
        last_time = time.time() - start_time
        total_times += last_time
    return total_times/test_times


if __name__ == "__main__":
    # all_data, target_data = load_list_data(10000, 1000)
    # all_data, target_data = load_list_data(100000, 1000)
    # all_data, target_data = load_list_data(1000000, 1000)

    # all_data, target_data = load_dict_data(10000, 1000)
    # all_data, target_data = load_dict_data(100000, 1000)
    # all_data, target_data = load_dict_data(1000000, 1000)
    all_data, target_data = load_dict_data(2000000, 1000)
    last_time = find_test(all_data, target_data)

    print(last_time)

上面分别用列表和字典的形式，模拟在规定的数据中，查找指定数量的元素所花费的时间。结论如下：
1、dict查找的性能远远大于list
2、在list中随着list数据的增大 查找时间会增大
3、在dict中查找元素不会随着dict的增大而增大

一个hash值存放一个key:value值。字典内部是通过hash表来映射的，那么什么是hash表呢？通过字典的key算出一个hash值，这个hash值对应表中的一个位置，这个位置存放着字典的key和value，又因为hash表的存放是连续的,类似于数组,它查找和存取是根据偏移量来进行的，因此不需要遍历，就能很快获取数据。

从上面可以得到下面几点结论：
1. dict的key或者set的值 都必须是可以hash的，不可变对象都是可hash的， str， fronzenset， tuple，以及自己实现的类若实现了 __hash__魔法函数
2. dict的内存花销大，存在一些剩余内存，但是查询速度快， 自定义的对象或者python内部的对象其实都是用dict来包装的
3. dict的存储顺序和元素添加顺序有关
4. 添加数据有可能改变已有数据的顺序（涉及到扩容的情况，也就是插入数据造成内存重新分配的时候）

在去重的时候，优先选用set去重，因为set占用空间比dict小，而且set可以对集合进行操作。