python的内存管理

计数器

垃圾回收机制

垃圾回收：引用计数为主，标记清除和分带回收为辅

1. 开启一个新的对象会存放到双端链表中
2. 通过引用计数来决定是不是垃圾，但是会有循环引用的问题
3. 为了解决循环引用，使用了标记清除，标记清除就是将循环引用的内容引用计数自动减一
4. 为了解决多次扫描一个双端链表，使用了分袋回收，一共3个袋，0袋，1袋，2袋
5. 当0袋的总长度>=700时扫描一下0袋，当0袋扫描10次后扫描一次1袋，扫描10次后计数仍大于等于1的进入1袋
6. 当1袋扫描10次后扫描一次2袋，1袋扫描10次后计数仍大于等于1的进入2袋

内存池

a = 3.14
del a
print(id(a))
b = 2.7
print(id(b)) #a和b的内存地址一样，因为有内存池的存在，浮点数和列表会使用和之前创建的对象同一内存地址

如何避免哈希冲突

可哈希？

如果一个对象在其生命周期内，其哈希值(可以通过python的内置函数hash获得)从未改变(这需要一个__hash__()方法)，并且可以与其他对象进行比较(这需要一个__eq__()或__cmp__()方法)，那么这个对象就是可哈希的。哈希对象的相等意味着其哈希值的相等。
哈希性使得对象可以用作dictionary键和set成员，因为这些数据结构在内部使用了哈希值。
Python的所有不可变的内置对象都是可hashable的，但可变容器(如列表或字典)并非如此。对于用户定义的类的实例，默认情况下是可哈希的；它们都是不相等的，并且它们的哈希值都是id()。

字典的实现原理

python中的字典底层依靠哈希表(hash table)实现, 使用开放寻址法解决冲突,
哈希表是key-value类型的数据结构, 可以理解为一个键值需要按照一定规则存放的数组, 而哈希函数就是这个规则
字典本质上是一个散列表(总有空白元素的数组, python至少保证1/3的数组是空的), 字典中的每个键都占用一个单元, 一个单元分为两部分, 分别是对键的引用和对值的引用, 使用hash函数获得键的散列值, 散列值对数组长度取余, 取得的值就是存放位置的索引，哈希冲突(数组的索引相同), 使用开放寻址法解决，这也是python中要求字典的key必须可hash的原因
数组中1/3的位置为空, 增加元素可能会导致扩容, 引发新的散列冲突, 导致新的散列表中键的次序发生变化, 这也是字典遍历时不能添加和删除的原因

hash算法与哈希冲突

• 哈希算法
  根据设定的哈希函数H（key）和处理冲突方法将一组关键字映象到一个有限的地址区间上的算法。也称为散列算法、杂凑算法。
• 哈希表
  数据经过哈希算法之后得到的集合。这样关键字和数据在集合中的位置存在一定的关系，可以根据这种关系快速查询。
• 非哈希表
  与哈希表相对应，集合中的 数据和其存放位置没任何关联关系的集合。
  由此可见，哈希算法是一种特殊的算法，能将任意数据散列后映射到有限的空间上，通常计算机软件中用作快速查找或加密使用。
• 哈希冲突
  由于哈希算法被计算的数据是无限的，而计算后的结果范围有限，因此总会存在不同的数据经过计算后得到的值相同，这就是哈希冲突。

解决哈希冲突的方法

解决哈希冲突的方法一般有：开放定址法、链地址法（拉链法）、再哈希法、建立公共溢出区等方法。

1 开放定址法
从发生冲突的那个单元起，按照一定的次序，从哈希表中找到一个空闲的单元。然后把发生冲突的元素存入到该单元的一种方法。开放定址法需要的表长度要大于等于所需要存放的元素。
在开放定址法中解决冲突的方法有：线行探查法、平方探查法、双散列函数探查法。
开放定址法的缺点在于删除元素的时候不能真的删除，否则会引起查找错误，只能做一个特殊标记。只到有下个元素插入才能真正删除该元素。

2 线行探查法
线行探查法是开放定址法中最简单的冲突处理方法，它从发生冲突的单元起，依次判断下一个单元是否为空，当达到最后一个单元时，再从表首依次判断。直到碰到空闲的单元或者探查完全部单元为止。
3 平方探查法
平方探查法即是发生冲突时，用发生冲突的单元d[i], 加上 12、 22等。即d[i] + 12，d[i] + 22, d[i] + 32...直到找到空闲单元。
在实际操作中，平方探查法不能探查到全部剩余的单元。不过在实际应用中，能探查到一半单元也就可以了。若探查到一半单元仍找不到一个空闲单元，表明此散列表太满，应该重新建立。
4 双散列函数探查法
这种方法使用两个散列函数hl和h2。其中hl和前面的h一样，以关键字为自变量，产生一个0至m—l之间的数作为散列地址；h2也以关键字为自变量，产生一个l至m—1之间的、并和m互素的数(即m不能被该数整除)作为探查序列的地址增量(即步长)，探查序列的步长值是固定值l；对于平方探查法，探查序列的步长值是探查次数i的两倍减l；对于双散列函数探查法，其探查序列的步长值是同一关键字的另一散列函数的值。
2 链地址法（拉链法）
链接地址法的思路是将哈希值相同的元素构成一个同义词的单链表，并将单链表的头指针存放在哈希表的第i个单元中，查找、插入和删除主要在同义词链表中进行。链表法适用于经常进行插入和删除的情况。
如下一组数字,(32、40、36、53、16、46、71、27、42、24、49、64)哈希表长度为13，哈希函数为H(key)=key%13,则链表法结果如下：

0       
1  -> 40 -> 27 -> 53 
2
3  -> 16 -> 42
4
5
6  -> 32 -> 71
7  -> 46
8
9
10 -> 36 -> 49
11 -> 24
12 -> 64 

注：在java中，链接地址法也是HashMap解决哈希冲突的方法之一，jdk1.7完全采用单链表来存储同义词，jdk1.8则采用了一种混合模式，对于链表长度大于8的，会转换为红黑树存储。

3 再哈希法
就是同时构造多个不同的哈希函数：
Hi = RHi(key) i= 1,2,3 ... k;
当H1 = RH1(key) 发生冲突时，再用H2 = RH2(key) 进行计算，直到冲突不再产生，这种方法不易产生聚集，但是增加了计算时间。

4 建立公共溢出区
将哈希表分为公共表和溢出表，当溢出发生时，将所有溢出数据统一放到溢出区。

python 内存管理

原文：https://www.cnblogs.com/muchengQ/p/11908410.html