字典、json、编码问题

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

1. Python的dict是一种数据结构，JSON是一种数据格式。形式上有些相像，但json是纯文本的，无法直接操作。
2. 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，如下所示。

参考文献

字符串和编码