题解 | #[C语言]设计LRU缓存结构#

题里面要求 set()和get()都是 O(1) 所以没啥说的，至少LRU中的每个数据需要双向链表存储，这样添加/删除/更新的时候才能做到 O(1)

为了实现通过key直接找到LRU中的数据，只能使用hash，这样才能满足O(1)，虽然会有冲突发生，但是也比每轮通过循环找key-value要好的多

// 双向链表节点结构
typedef struct element_s{
    struct element_s* prev;
    struct element_s* next;
    int value;
    int key;
}element_t;

// 双向链表结构
typedef struct list_s{
    element_t *head;
    element_t *tail;
    int k;
}list_t;

// hash表节点结构
typedef struct hash_element_s{
    struct hash_element_s * next;
    element_t* value;
}hash_element_t;

// hash表结构
typedef struct hash_s{
	hash_element_t **hash;
	int hash_size;
}hash_t;

// hash表加入新节点，使用链表方式解决冲突
static void
hash_set_value(hash_t* hash_table,int key,element_t* element)
{
	unsigned int _key = (unsigned int)key;
    if(hash_table->hash[(_key)%hash_table->hash_size] == NULL)
    {
        hash_table->hash[(_key)%hash_table->hash_size] = (hash_element_t*)malloc(sizeof(hash_element_t));
        hash_table->hash[(_key)%hash_table->hash_size]->next = NULL;
        hash_table->hash[(_key)%hash_table->hash_size]->value = element;
    }else{
        hash_element_t* hash_element_priv = hash_table->hash[(_key)%hash_table->hash_size];
        hash_element_t* hash_element = hash_element_priv->next;
        while(hash_element != NULL)
        {
            hash_element_priv = hash_element;
            hash_element = hash_element->next;
        }
        hash_element_priv->next = (hash_element_t*)malloc(sizeof(hash_element_t));
        hash_element = hash_element_priv->next;
        hash_element->next = NULL;
        hash_element->value = element;
    }
}

// hash表获取value
static element_t*
hash_get_value(hash_t* hash_table,int key)
{
	unsigned int _key = (unsigned int)key;
	hash_element_t* hash_element = hash_table->hash[(_key)%hash_table->hash_size];

    while(hash_element != NULL && hash_element->value->key != key)
        hash_element = hash_element->next;

    if(hash_element != NULL && hash_element->value->key == key)
        return hash_element->value;
    return NULL;
}

// hash表移除key-value对
static void
hash_remove_value(hash_t* hash_table,int key)
{
	unsigned int _key = (unsigned int)key;
    hash_element_t* hash_element = hash_table->hash[(_key)%hash_table->hash_size];
    hash_element_t* hash_element_priv = NULL;
	
	while(hash_element != NULL && hash_element->value->key != key)
    {
        hash_element_priv = hash_element;
        hash_element = hash_element->next;
    }

    if(hash_element != NULL && hash_element->value->key == key)
    {
        if(hash_element_priv != NULL)
        {
            hash_element_priv->next = hash_element->next;
            free(hash_element);
        }else{
            hash_table->hash[(_key)%hash_table->hash_size] = hash_element->next;
            free(hash_element);
        }
    }
}


static hash_t*
hash_init(int size)
{
    hash_t* hash_table = (hash_t*)malloc(sizeof(hash_t));
    hash_table->hash_size = size;
    hash_table->hash = (hash_element_t**)malloc(sizeof(hash_element_t*)*hash_table->hash_size);
    memset(hash_table->hash,0,sizeof(hash_element_t*)*hash_table->hash_size);
    
    return hash_table;
}

static void
hash_destroy(hash_t* hash_table)
{
    for(int i=0;i<hash_table->hash_size;++i)
	{
		hash_element_t *temp, *hash_element = hash_table->hash[i];
		while(hash_element)
		{
            temp = hash_element;
            hash_element = hash_element->next;
			free(temp);
		}
	}
    free(hash_table->hash);
    free(hash_table);
}

// 更新双向链表，将新节点或者刚刚访问的节点，放到双向链表的tail部分，head部分是最久未使用的节点
static int
update_list(list_t* list,hash_t* hash_table,int key,element_t *element)
{
	element_t *update=NULL;
	if(element == NULL)
		update = hash_get_value(hash_table,key);
	else
		update = element;
		
	if(update == NULL) 
		return -1;
    	
	if(list->head == list->tail)
		return update->value;
	
	if(list->head == update)
	{
		list->head = update->next;
		update->prev = list->tail;
        update->next->prev = NULL;
        update->next = NULL;
        list->tail->next = update;
        list->tail = update;
	}else if(list->tail != update){
		update->prev->next = update->next;
        update->next->prev = update->prev;
        update->next = NULL;
        update->prev = list->tail;
        list->tail->next = update;
        list->tail = update;
	}else ;
	
	//printf("k=%lld v=%lld\n",update->key,update->value);
	return update->value;
}

// 双向链表获取key-value
static int
list_get_value(list_t* list,hash_t* hash_table,int key)
{
    return update_list(list,hash_table,key,NULL);
}

static void
insert_list(list_t* list,hash_t* hash_table,int key ,int value)
{
	element_t *element = hash_get_value(hash_table,key);
    if(element != NULL) //update pos
    {
    	if(update_list(list,hash_table,key,element) != value)
    		element->value = value;
    }else{
        if(list->k > 0) //insert at tail
        {
            element_t *new_elem = (element_t *)malloc(sizeof(element_t));
            hash_set_value(hash_table,key,new_elem);
            
            if(list->head == NULL) 
            {
            	list->tail = list->head = new_elem;
                new_elem->next = new_elem->prev = NULL;
			}else{
            	new_elem->prev = list->tail;
	            new_elem->next = NULL;
	            list->tail->next = new_elem;
	            list->tail = new_elem;
			}
            new_elem->key = key;
            new_elem->value = value;
            --list->k;
        }else{  // replace
            element_t *update = list->head;
            update_list(list,hash_table,update->key,update);
			update->value = value;
            hash_remove_value(hash_table,update->key);
			hash_set_value(hash_table,key,update);
            update->key = key;
        }
    }
}


int * LRU(int** operators, int operatorsRowLen, int* operatorsColLen, int k, int* returnSize ) {
    *returnSize = 0;
    list_t g_list={NULL,NULL,k};
    hash_t* hash_table = hash_init(10*k);
    int result_size=0;
    int *res;

  	// 计算返回值数组的大小
    for(int i=0;i<operatorsRowLen;++i)
    {
        if(operatorsColLen[i]==2)
            ++result_size;
    }
    res=(int*)malloc(sizeof(int)*result_size);
    
    for(int i=0;i<operatorsRowLen;++i)
    {
        if(operatorsColLen[i]==2){
            res[(*returnSize)++] = list_get_value(&g_list,hash_table,operators[i][1]);
        }else{
            insert_list(&g_list,hash_table,operators[i][1],operators[i][2]);
        }
    }
    hash_destroy(hash_table);

    return res;
}