Time Complexity
Worst Case
Search : O(n)
Insertion : Access 후에도 삽입지점까지 최대 n번 이동해야 함 - O(n)
Deletion : Access 후에도 삭제지점까지 최대 n번 이동해야 함 - O(n)
Average Case
Search : Theta(1)
Insertion : Theta(1)
Deletion : Theta(1)
Space Complexity
Worst Case
O(n)
Example
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define HASH_SIZE 10
typedef struct _node {
struct _node *next;
char *value;
} Node;
typedef struct _hashTable {
Node *table[HASH_SIZE];
} HashTable;
Node *createNode() {
Node *node = (Node *) malloc(sizeof(Node));
node->next = NULL;
node->value = NULL;
return node;
}
HashTable *createHashTable() {
HashTable *hashTable = (HashTable *) malloc(sizeof(HashTable));
for(int i=0;i<HASH_SIZE;i++) hashTable->table[i] = NULL;
return hashTable;
}
int hash(char *value) {
int hashed = 0;
for(int i=0;i<strlen(value);i++) {
hashed += (hashed << 4) + value[i];
}
return hashed % HASH_SIZE;
}
void push(HashTable *hashTable, char *value) {
int index = hash(value);
Node *newNode = createNode();
newNode->value = value;
Node *current = hashTable->table[index];
if (current != NULL) {
while(current->next != NULL) {
current = current->next;
}
current->next = newNode;
}
else {
hashTable->table[index] = newNode;
}
}
int search(HashTable *hashTable, char *value) {
int index = hash(value);
Node *current = hashTable->table[index];
while(current != NULL) {
if (strcmp(current->value, value) == 0) {
return 1;
}
current = current->next;
}
return 0;
}
void print(HashTable *hashTable) {
for(int i=0;i<HASH_SIZE;i++) {
if(hashTable->table[i]) {
Node *current = hashTable->table[i];
while(current != NULL) {
printf("table[%d] %s\n", i, current->value);
current = current->next;
}
}
}
}
int main() {
HashTable *hashTable = createHashTable();
push(hashTable, "hello");
push(hashTable, "world");
push(hashTable, "hash");
push(hashTable, "table");
print(hashTable);
printf("%d ", search(hashTable, "hello"));
printf("%d ", search(hashTable, "world"));
printf("%d ", search(hashTable, "hash"));
printf("%d ", search(hashTable, "table"));
printf("%d ", search(hashTable, "hell"));
return 0;
}
Remark
스트링 해시의 경우 여러 방법이 있지만 아래 방법을 사용함
int hash(char *value) {
int hashed = 0;
for(int i=0;i<strlen(value);i++) {
hashed += (hashed << 4) + value[i];
}
return hashed % HASH_SIZE;
}