1. 字典
1.1 基础概念
在Python中,字典是通过散列表或说哈希表实现的。字典本质上也是一个数组,但数组的索引是键经过哈希函数处理后得到的散列值,所以接下来好好咱们聊聊hash这个东西。
hash函数翻译过来叫做散列函数,又称哈希函数。通过把关键码值(key-value对)映射到表中一个位置来访问记录,以加快查找的速度。HashTable 的核心思想是对于每一个数据,根据某种给定的 Hash 函数,计算出数据的散列值,然后根据散列值来进行查找。但是不同的数据仍有一定记录产生相同的散列值的,这种状况称作“哈希碰撞”,优秀的哈希函数应该尽可能的降低产生数据碰撞的几率。
一般情况下普通的顺序表数组存储结构也可以认为是简单的哈希表,虽然没有采用哈希函数(取余),但同样可以在O(1)时间内进行查找和修改。但是这种方法存在两个问题:扩展性不强;浪费空间。
1.2 常见的哈希碰撞解决方法:
1.2.1 开放寻址法(open addressing)
开放寻址法中,所有的元素都存放在散列表里,当产生哈希冲突时,通过一个探测函数计算出下一个候选位置,如果下一个获选位置还是有冲突,那么不断通过探测函数往下找,直到找个一个空槽来存放待插入元素。
开放地址的意思是除了哈希函数得出的地址可用,当出现冲突的时候其他的地址也一样可用,常见的开放地址思想的方法有线性探测再散列,二次探测再散列等,这些方法都是在第一选择被占用的情况下的解决方法。
1.2.2 再哈希法
这个方法是按顺序规定多个哈希函数,每次查询的时候按顺序调用哈希函数,调用到第一个为空的时候返回不存在,调用到此键的时候返回其值。
1.3.3 链地址法
将所有关键字哈希值相同的记录都存在同一线性链表中,这样不需要占用其他的哈希地址,相同的哈希值在一条链表上,按顺序遍历就可以找到,即数组和链表的结合,这种方法也是java的hash table实现方法,最新的java方法中把链表改进为了红黑树来实现。
2. 有序字典
# 有序字典的作用只是记住元素插入顺序并按顺序输出。
# 如果有序字典中的元素一开始就定义好了,后面没有插入元素这一动作,那么遍历有序字典,其输出结果仍然是无序的.
# 因为缺少了有序插入这一条件,所以此时有序字典就失去了作用,所以有序字典一般用于动态添加并需要按添加顺序输出的时候。
from collections import OrderedDict
a = OrderedDict()
b = dict()
a['1'] = 1
a['2'] = 2
a['3'] = 3
b['1'] = 1
b['2'] = 2
b['3'] = 3
print a
print b
======================
OrderedDict([('1', 1), ('2', 2), ('3', 3)])
{'1': 1, '3': 3, '2': 2}
3. json
- Python的
dict
是一种数据结构,JSON
是一种数据格式。形式上有些相像,但json是纯文本的,无法直接操作。 dict
字符串用单引号,json
强制规定双引号。
json(str),dict转换:
import json
# str(json)转dict
json.loads(str)
# dict转json(str)
json.dumps(j)
4. 编码问题
ASCII编码:1字节(byte),即8个比特位(bit)来编码,最多只能满足256个唯一标识,使用于英文,不适用于中文
Unicode编码:2字节,即16位来编码,能表示的字符更多,但会耗费较多的空间(英文只需1字节即可,Unicode强制编码为两字节)
UTF-8编码:UTF-8编码把一个Unicode字符根据不同的数字大小编码成1-6个字节,常用的英文字母被编码成1个字节,汉字通常是3个字节,只有很生僻的字符才会被编码成4-6个字节。如果你要传输的文本包含大量英文字符,用UTF-8编码就能节省空间;此外ASCII编码可以看做是UTF-8编码的一部分,utf-8编码兼容ASCII,如下所示。