大家好，欢迎来到IT知识分享网。

一、定义

• 散列表（Hash table，也叫哈希表），是根据关键码值(Key和value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

• 给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。

• 个人理解：与列表不同的是，哈希表的索引是Key，直接通过Key值访问value，而不同于列表，通过整数$[0,\infty )$作为索引存储值。

二、冲突

对不同的关键字可能得到同一散列地址，即k1≠k2，而f(k1)=f(k2)，这种现象称为冲突（英语：Collision）。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数f(k)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为散列表，这一映射过程称为散列造表或散列，所得的存储位置称散列地址。

三、Python中的应用

3.1 字典

Python中的字典便应用了哈希表的原理，能使关键字和值一一对应。

• 字典的初始化：

a = dict()
b = {}
c = {'a': 1, 'b': 2, 'b': '3'}  # 冒号左边是key，右边是value，由于存在重复的b，最后剩下右边的'b':3

• 访问字典中的value

print "c['a']: ", c['a']

• 修改字典

c['a'] = 0 # 将原来映射的1变为0
c['c'] = 4 # 添加新的键值对

• 删除字典元素

del c['a'] #删除key为a的键值对
c.clear #清除字典c中所有的键值对
del c #直接删除字典c

• 字典内置函数和方法

leetcode中的应用

1. 两数之和（twosum）

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        map_a = dict()
        k = len(nums)
        for i in range(0, k):   #一边将列表中的数添加到字典中，一边判断两数之差是否存在于字典中
            temp = target - nums[i]  
            if temp in map_a :  # 判断步骤
                return [map_a[temp], i]
            map_a[nums[i]] =  i  # 添加步骤（切记先判断再添加，以免key冲突）

• 提交结果：

• 时间复杂度：
  因为有循环，最坏的情况是循环n次(用n表示k)，时间复杂度为o(n)

2. 快乐数()

class Solution(object):
    def isHappy(self, n):
        """
        :type n: int
        :rtype: bool
        """

        dict_1 = {}

        while 1:
            sum = 0

            while n != 0:   #计算平方之和
                sum += (n % 10) ** 2
                n /= 10

            n = sum

            if n == 1:   #如果平方之和为1，证明n是快乐数，返回True
                return True
            elif dict_1.has_key(n):  #若平方之和已出现过（循环计算），证明加法之和不可能为1，n不是快乐数，返回False
                return False

            dict_1[n] = 0

提交结果：

• 时间复杂度：
  时间复杂度不好计量，随着不断计算，应该不会很大