[SWEA] 7-8. Hash

2.実戦講座
2.1 djb2
djb 2は文字列のhash関数の1つであり、ランダム分布を簡略化することができる.magicnumberと呼ばれる5381および33を使用してhashキーを生成する.
djb 2のコードは以下の通りです.

unsigned long djb2(const char* str)
{
    unsigned long hash = 5381; // base
    int c;
    while (c = *str++)
    {
        hash = (((hash << 5) + hash) + c); // hash = hash * 33 + ascii code of str[i]
    }
    return hash % HASH_TABLE_SIZE;
}

2.2 Hash Collision(衝突)
ハッシュ・テーブルのサイズは、デフォルトではhash関数として現れるhash idxの範囲よりも小さいため、常に競合する可能性があります.競合を解決するには、次の方法を使用します.
2.2.1 Open addressing
競合が発生した場合は、ハッシュ・テーブルの他の場所として保存されます.
2.2.2 Chaining
リンクリストを使用して競合を解決する方法.(主な使い方)
2.2.3効率的なハッシュ関数の使用
データの分布を均一にし、衝突の可能性を低減します.(djb 2の使用を推奨)
2.3適切なハッシュ・テーブル・サイズ
通常は2*Nに最も近い小数または2 mの値を使用します.
それぞれに欠点があるTable sizeとして小数を使用する場合は、より遅い%演算子を使用する必要があります.2 mを使用すると、ビットシールドで高速に計算できます.
しかしhash関数がサブビットを均一に分布できない場合、m未満のサブビットを使用するため、多くの競合が発生する.したがって,良いhash関数を用いることが重要である.
また,2 mはrehashにも有利であるため,JavaはhashMapのsizeを2の繰返し二乗として用いる.
Java: A “prime” number or a “power of two” as HashMap size?
https://stackoverflow.com/questions/15437345/java-a-prime-number-or-a-power-of-two-as-hashmap-size
しかし、小数または2の反復二乗または糖楽には影響しなかった.
便利な方法を使えばいい
10007、20011、30011、4009、10003、200003はよく使われる小数で、小数を使う方は参考にしてください.
2.4実施練習
hashデータ構造におけるメンバー関数の追加、検索、削除の例を直接実現します.
input dataの条件.
1.add最大100000
2.keyは小文字からなる文字列で、長さは2~10です.
3.存在しない鍵が見つかったり削除されたりしていない場合.

#define HASH_SIZE (1 << 18)
#define MAXN 100000
#define DIV (HASH_SIZE - 1)

typedef unsigned long long ll;


bool strCmp(char a[], char b[]) {
	int i = 0;

	for (; a[i]; i++) {
		if (a[i] != b[i]) {
			return false;
		}
	}
	return a[i] == b[i];
}

void strCpy(char dst[], char src[]) {
	while (*src) {
		*dst++ = *src++;
	}

	*dst = 0;
}


struct Node {
	char key[11];
	int data;
	Node *next;

	Node *alloc(char _key[], int _data, Node *_next) {
		strCpy(key, _key);
		data = _data;
		next = _next;
		return this;
	}

	/* 찾는 node의 바로 이전 node를 반환한다. */
	Node *getPrevNode(char _key[]) {
		Node *ptr = this;

		while (ptr->next) {
			if (strCmp(_key, ptr->next->key)) {
				break;
			}
			ptr = ptr->next;
		}

		return ptr;
	}
};


int bCnt;
Node buf[MAXN];
Node hashTable[HASH_SIZE];


void init()
{
	bCnt = 0;
	for (int i = 0; i < HASH_SIZE; ++i) {
		hashTable[i].next = 0;
	}
}


int getKey(char str[]) {
	ll key = 5381;

	for (int i = 0; str[i]; ++i) {
		key = ((key << 5) + key) + (str[i] - 'a' + 1);
	}

	return (int) (key & DIV);	// 해당 code에서 hash값은 unsigned long long범위를 초과할 일이 없음.
}


int find(char key[])
{
	Node *prevNode;
	int target = getKey(key);
	prevNode = hashTable[target].getPrevNode(key);

	return prevNode->next->data;
}


void add(char key[], int data)
{
	int target = getKey(key);
	hashTable[target].next = buf[bCnt++].alloc(key, data, hashTable[target].next);
}


int remove(char key[])
{
	Node *prevNode, *targetNode;
	int target = getKey(key);
	prevNode = hashTable[target].getPrevNode(key);
	targetNode = prevNode->next;

	prevNode->next = targetNode->next;
	return targetNode->data;
}

1.Hash tableは通常変数として宣言され、ヘッダーとして使用されます.
2.Chainingはlinklistとして実装される.
3.Single Linked Listは前のノードに戻って削除しています.
4.元のデータ(キーワード文字列)をハッシュにコピーするのは、競合のためです.
競合が発生した場合、2つ以上のノードは同じhash値を有します.
ハッシュ値は通常復号できないため、元のデータはわかりません.