Leetcode 127 -- 哈希表

题目描述

217

手写哈希表

class Solution {
public:#define DEFAULT_LEN 16#define DEFAULT_FACTOR 0.75fconst float factor = DEFAULT_FACTOR;typedef struct node{int key;int val;struct node* next;}Node;typedef struct {int capacity;int size;Node** set;} MyHashMap;MyHashMap* init() {MyHashMap* ret =  (MyHashMap*)malloc(sizeof(MyHashMap));ret->capacity = DEFAULT_LEN;ret->size = 0;ret->set = (Node**)calloc(DEFAULT_LEN,sizeof(Node*));return ret;}inline unsigned int getIndex(unsigned int key,int capacity){return (key^(key>>16))&(capacity-1);}void insert(MyHashMap* obj,Node* node){int index = getIndex(node->key,obj->capacity);node->next = obj->set[index];obj->set[index] = node;}void rehash(MyHashMap* obj,Node** tmp){int preSize = obj->capacity / 2;for(int i=0;i<preSize;i++){if(tmp[i]!=NULL){Node * pre;Node * cur = tmp[i];while (cur!=NULL){pre = cur;cur = cur->next;insert(obj,pre);}}}}void resize(MyHashMap* obj){obj->capacity <<= 1;Node ** tmp = obj->set;obj->set = (Node**)calloc(obj->capacity,sizeof(Node*));rehash(obj,tmp);free(tmp);}void Put(MyHashMap* obj, int key,int value) {if(obj->size>=factor*obj->capacity)resize(obj);int index = getIndex(key,obj->capacity );if(obj->set[index]==NULL){Node * t = (Node*)malloc(sizeof(Node));t->key = key;t->val = value;t->next = NULL;obj->set[index] = t;obj->size++;return;}Node* head = obj->set[index];Node* t = head;while (t!=NULL){if(t->key==key){t->val = value;return;}t = t->next;}Node* node = (Node*)malloc(sizeof(Node));node->key = key;node->val = value;node->next = head;obj->set[index] = node;obj->size++;}void Remove(MyHashMap* obj, int key) {int index = getIndex(key,obj->capacity);Node *head = obj->set[index];Node *pre;Node *cur = head;if(cur==NULL)return;if(cur->key == key){pre = cur;cur = cur->next;free(pre);obj->set[index] = cur;return;}while (cur!=NULL){pre = cur;cur = cur->next;if(cur!=NULL&&cur->key == key){pre->next = cur->next;free(cur);return;}}}int* Get(MyHashMap* obj, int key) {int index = getIndex(key,obj->capacity);Node * head = obj->set[index];while (head != NULL){if(head->key == key)return &(head->val);head = head->next;}return NULL;}void del_node(Node* head){Node * pre;Node * cur = head;while (cur!=NULL){pre = cur;cur = cur->next;free(pre);}}void Free(MyHashMap* obj) {for(int i=0;i<obj->capacity;i++){del_node(obj->set[i]);}}bool containsDuplicate(vector<int>& nums) {MyHashMap* set = init();int n = nums.size();for (int i = 0; i < n; i++) {if(Get(set,nums[i])!=NULL)return true;Put(set,nums[i],0);}return false;}
};