数据结构-4-散列表(哈希表)

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

散列表（哈希表）

实现一个基于链表法解决冲突问题的散列表

参考：https://www.cnblogs.com/linxiyue/p/3795396.html

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
class _ListNode(object):
    def __init__(self,key):
        self.key=key
        self.next=None
class HashMap(object):
    def __init__(self,tableSize):
        self._table=[None]*tableSize
        self._n=0  #number of nodes in the map
    def __len__(self):
        return self._n
    def _hash(self,key):
        return abs(hash(key))%len(self._table)
    def __getitem__(self,key):
        j=self._hash(key)
        node=self._table[j]
        while node is not None and node.key!=key :
            node=node.next
        if node is None:
            raise KeyError,'KeyError'+repr(key)
        return node       
    def insert(self,key):
        try:
            self[key]
        except KeyError:
            j=self._hash(key)
            node=self._table[j]
            self._table[j]=_ListNode(key)
            self._table[j].next=node
            self._n+=1
    def __delitem__(self,key):
        j=self._hash(key)
        node=self._table[j]
        if node is not None:
            if node.key==key:
                self._table[j]=node.next
                self._-=1
            else:
                while node.next!=None:
                    pre=node
                    node=node.next
                    if node.key==key:
                        pre.next=node.next
                        self._n-=1
                        break

实现一个 LRU 缓存淘汰算法

LRU全称是Least Recently Used，即最近最久未使用的意思。

LRU算法的设计原则是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。

使用dict和list实现

比较自然的想法：使用dict存<key,value>，使用list记录访问顺序，索引[0,…,capacity-1]，越小表示访问时间越近，每次pop()删除最末尾的元素。

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
# coding: utf-8

class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity
        self.lru_cache = {}
        self.sort_list = []  # 访问顺序

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key in self.lru_cache:
            value = self.lru_cache[key]
            self.sort_list.remove(key)
            self.sort_list.insert(0, key)
        else:
            value = -1
        print("get", key, ": ", self.lru_cache, self.sort_list)
        return value

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """
        if key in self.lru_cache:
            self.lru_cache[key] = value
            self.sort_list.remove(key)
            self.sort_list.insert(0, key)
        else:
            if len(self.sort_list) == self.capacity:
                last_key = self.sort_list.pop()
                self.lru_cache.pop(last_key)
            self.sort_list.insert(0, key)
            self.lru_cache[key] = value

        print("put <", key, ":", value, ">: ", self.lru_cache, self.sort_list)


# Your LRUCache object will be instantiated and called as such:
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print("get value is: ",cache.get(1))
cache.put(3, 3)
cache.put(4, 4)
print("get value is: ",cache.get(1))
print("get value is: ",cache.get(3))
print("get value is: ",cache.get(5))

"""
put < 1 : 1 >:  {1: 1} [1]
put < 2 : 2 >:  {1: 1, 2: 2} [2, 1]
get 1 :  {1: 1, 2: 2} [1, 2]
get value is:  1
put < 3 : 3 >:  {1: 1, 3: 3} [3, 1]
put < 4 : 4 >:  {3: 3, 4: 4} [4, 3]
get 1 :  {3: 3, 4: 4} [4, 3]
get value is:  -1
get 3 :  {3: 3, 4: 4} [3, 4]
get value is:  3
get 5 :  {3: 3, 4: 4} [3, 4]
get value is:  -1
"""

对应的 LeetCode 练习题

哈希表

并完成leetcode上的两数之和(1)及Happy Number(202)！(要求全部用哈希思想实现！)

leetcode-1-两数之和

代码见：leetcode-1-两数之和 中”方法二”，使用dict记录当前元素下标和匹配的值

LeetCode-202-快乐数Happy Number

使用dict记录求过的数

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
class Solution(object):                                    
    def isHappy(self, n):                                  
        """                                                
        :type n: int                                       
        :rtype: bool                                       
        """                                                
        m_dict = {}                                        
        while n != 1:                                      
            # print(n)                                     
            n = sum(int(i) ** 2 for i in str(n))           
            if n in m_dict:                                
                return False                               
            m_dict[n] = 1                                  
        return True                                        
                                                                                                                  
s = Solution()                                             
print(s.isHappy(19))                                       
                                                           
"""                                                        
19                                                         
82                                                         
68                                                         
100                                                        
True                                                       
"""