散列表
- 实现一个基于链表法解决冲突问题的散列表
- 实现一个LRU缓存淘汰算法
/*链接法解决哈希散列碰撞问题*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#define N 20 //数组数量
#define Nhash 7 //哈希槽的数量
#define N_R 200
//每个数据结点
typedef struct node{
int key;
int num;
struct node * next;
struct node * pre;
}Node, *Pnode;
//哈希链表
typedef struct Hash{
Pnode link[N]; //每个链表的表头指针
int num; //哈希表中现存数据
int len; //哈希数组长度
}hash,*Phash;
Pnode IniPnode(int key){
Pnode p=(Pnode)malloc(sizeof(Node));
p->key=key;
p->num=1;
p->next=NULL;
p->pre=NULL;
}
//散列位置计算，当前使用取余数法
int HashPos(int key){
return key % Nhash;
}
Pnode FindNodePos(Phash h, int key){
int pos=HashPos(key);
Pnode link = h->link[pos];
while(link->next != NULL && link->key != key){
link=link->next;
}
return link;
}
void IniHash(Phash *h, int len){
int i;
*h=(Phash)malloc(sizeof(hash));
for(i=0;i<len;i++){
(*h)->link[i] = IniPnode(-1); //头结点
}
(*h)->num =0; //总数为0
(*h)->len=len;
}
void Insert(Phash h, int key){
Pnode p=FindNodePos(h,key);
if(p->next != NULL) p->num ++;
else{
Pnode q =IniPnode(key);
p->next = q;
q->pre=p;
}
++ h->num ;
}
Pnode Search(Phash h, int key){
Pnode p=FindNodePos(h,key);
if(p->next = NULL) return NULL;
else return p;
}
int Delete(Phash h, int key){
Pnode p=FindNodePos(h,key);
p->pre->next=p->next;
free(p);
}
void PrintLink(Pnode p){
while(p->next!=NULL){
printf("[key=%d|num=%d] -> ",p->next->key,p->next->num);
p=p->next;
}
//printf("[key=%d|num=%d]",p->key,p->num);
printf("
");
}
void PrintHash(Phash h){
int i;
printf("哈希表中公有结点%d个
",h->num);
for(i=0;i<h->len;i++){
printf("%d ",i);
PrintLink(h->link[i]);
}
}
void DeleteHash(Phash h){
int i;
for(i=0;i<h->num;i++){
free(h->link[i]);
}
free(h);
}
int main(){
int i, a[N];
Phash h=NULL; //哈希数组链表头结点
IniHash(&h,Nhash);
srand((unsigned)time(NULL));
for(i=0;i<N;i++){
a[i]=rand()%N_R;
Insert(h,a[i]);
printf("%d ",a[i]);
}
printf("
");
PrintHash(h);
for(i=0;i<N;i++){
Delete(h,a[i]);
}
DeleteHash(h);
system("pause");
return 0;
}
# -*- coding: utf-8 -*-
"""
"""
class Node:
def __init__(self,key,value):
self.key=key
self.value=value
self.next=None
class ChainHash:
def __init__(self,capacity):
self.capacity=capacity
self.table=[None]*capacity
def buildHash(self,lista):
for i in range(len(lista)):
value=int(lista[i])
key=value % 13
print(key)
node_=self.table[key]
if node_ is None:
self.table[key]=Node(key,value)
else:
while node_.next is not None:
if node_.key == key:
node_.value = value
return
node_ = node_.next
node_.next = Node(key, value)
def InsertHash(self,value):
key=value % 13
node_=self.table[key]
if node_ is None:
self.table[key]=Node(key,value)
else:
while node_.next is not None:
if node_.key == key:
node_.value = value
return
node_ = node_.next
node_.next = Node(key, value)
def SearchHash(self,key,value):
node_ = self.table[key]
while node_ is not None:
if node_.value == value:
return node_ # 返回该指针位置
node_ = node_.next
return None # 若没有找到该数值，则返回空
# In[]
if __name__ == '__main__':
s=ChainHash(20)
lista=[1,6,11,14,19]
# In[]
s.buildHash(lista)
# In[]
s.InsertHash(27)
# print(s.table)
# In[]
print(s.SearchHash(1,17))
LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。
原理：
利用list记录key的次序，每次set,或get操作将key插入到list首位。
缓冲区满之后再出现set操作，移除末尾的key。
key in dict判断key是否出现过
class LRUcache:
def __init__(self, size=3):
self.cache = {}
self.keys = []
self.size = size
def get(self, key):
if key in self.cache:
self.keys.remove(key)
self.keys.insert(0, key)
return self.cache[key]
else:
return None
def set(self, key, value):
if key in self.cache:
self.keys.remove(key)
self.keys.insert(0, key)
self.cache[key] = value
elif len(self.keys) == self.size:
old = self.keys.pop()
self.cache.pop(old)
self.keys.insert(0, key)
self.cache[key] = value
else:
self.keys.insert(0, key)
self.cache[key] = value
if __name__ == '__main__':
test = LRUcache()
test.set('a',2)
test.set('b',2)
test.set('c',2)
test.set('d',2)
test.set('e',2)
test.set('f',2)
print(test.get('c'))
print(test.get('b'))
print(test.get('a'))