반응형
해시란
해시는 입력 받은 데이터를 완전히 다른 형태의 데이터로 바꾸는 작업
사용처
- 해시 테이블
- 암호화
- 데이터 축약
해시 테이블이란
공간을 소비해서 속도를 올린 알고리즘.
테이블을 만들어 해시 값을 참고하여 데이터를 찾는 방식
데이터는 해시 함수를 거쳐서 해시 테이블의 주소로 변환되고 이를 참고 하는 방식
해시 함수란
데이터를 가공하여 해시 테이블내의 주소 값으로 저장하는 함수
해싱 함수 종류
- 나눗셈법 : 입력 값을 테이블 크기(소수 선호)로 나누고, 나머지를 테이블 주소로 사용
ex ) 입력 % 테이블 크기 = 주소
- 자릿수 접기 : 입력 값을 아스키 코드화 하여 총합을 주소로 사용
해싱 충돌
해싱 함수를 통해 서로 다른 데이터의 주소가 같은 주소를 가지게 되는 충돌하는 경우
해싱 충돌 해결 방법
- 개방 해싱 : 해시 테이블 주소 외부에서 새로운 공간을 할당하고 문제를 수습
- 폐쇄 해싱 : 해시 테이블 주소 내부에서 문제를 수습
1. 체이닝 : 충돌이 발생하면 해당 주소에 데이터들을 링크드 링스트로 줄줄이 연결하는 기법
-> 성능을 더 올리려면 이진 탐색 트리 + 해시 테이블 이용
2. 개방 주소법 : 충돌이 발생하면 해시 함수로 얻은 주소가 아닌 다른 주소를 얻음으로 문제를 해결하는 기법
- 선형 탐사 : 얻은 주소의 다음 주소로 순차적으로 1씩 이동하는 기법
- 제곱 탐사 : 얻은 주소의 다음 주소로 이동시 제곱으로 이동하는 기법(1->1, 2->4...)
- 이중 해싱 : 충돌 발생 시 새로운 해싱 함수를 이용하여 다른 주소를 할당하는 기법
-> key%13 에서 충돌하면 key%11에서 다시 해봄
- 재해싱 : 남아 있는 공간이 얼마 남지 않은 경우 충돌이 자주 발생하여 성능이 떨어지기 때문에 공간 사용률이 70~80%에 달하면 테이블의 크기를 늘리는 기법
C 소스
SimpleHashTable
SimpleHashTable.h
/*
* SimpleHashTable.h
*
* Created on: 2019. 1. 7.
* Author: otrodevym
*/
#ifndef SIMPLEHASHTABLE_H_
#define SIMPLEHASHTABLE_H_
#include <stdio.h>
#include <stdlib.h>
typedef int KeyType;
typedef int ValueType;
typedef struct tagNode{
KeyType Key;
ValueType Value;
} Node;
typedef struct tagHashTable{
int TableSize;
Node* Table;
} HashTable;
HashTable* SHT_CreateHashTable(int TableSize);
void SHT_Set(HashTable* HT, KeyType Key, ValueType Value);
ValueType SHT_Get(HashTable* HT, KeyType Key);
void SHT_DestroyHashTable(HashTable* HT);
int SHT_Hash(int Key, int TableSize);
int MyHash(char* ChKey, int keyLength, int TableSize);
#endif /* 8_1_SIMPLE_HASH_TABLE_SIMPLEHASHTABLE_H_ */
SimpleHashTable.c
/*
* SimpleHashTableMain.c
*
* Created on: 2019. 1. 7.
* Author: otrodevym
*/
#include "SimpleHashTable.h"
int SimpleHashTableMain(){
HashTable* HT = SHT_CreateHashTable(193);
SHT_Set(HT, 418, 32114);
SHT_Set(HT, 9, 514);
SHT_Set(HT, 27, 8917);
SHT_Set(HT, 1031, 286);
printf("Key : %d, Value : %d \n", 418, SHT_Get(HT, 418));
printf("Key : %d, Value : %d \n", 9, SHT_Get(HT, 9));
printf("Key : %d, Value : %d \n", 27, SHT_Get(HT, 27));
printf("Key : %d, Value : %d \n", 21031, SHT_Get(HT, 1031));
char* ch = "asdasd";
int result = MyHash(ch, 100, 193);
printf("result : %d ", result);
SHT_DestroyHashTable(HT);
return 0;
}
SimpleHashTableMain.c
/*
* SimpleHashTableMain.c
*
* Created on: 2019. 1. 7.
* Author: otrodevym
*/
#include "SimpleHashTable.h"
int SimpleHashTableMain(){
HashTable* HT = SHT_CreateHashTable(193);
SHT_Set(HT, 418, 32114);
SHT_Set(HT, 9, 514);
SHT_Set(HT, 27, 8917);
SHT_Set(HT, 1031, 286);
printf("Key : %d, Value : %d \n", 418, SHT_Get(HT, 418));
printf("Key : %d, Value : %d \n", 9, SHT_Get(HT, 9));
printf("Key : %d, Value : %d \n", 27, SHT_Get(HT, 27));
printf("Key : %d, Value : %d \n", 21031, SHT_Get(HT, 1031));
char* ch = "asdasd";
int result = MyHash(ch, 100, 193);
printf("result : %d ", result);
SHT_DestroyHashTable(HT);
return 0;
}
Chining
Chining.h
/*
* Chining.h
*
* Created on: 2019. 1. 7.
* Author: otrodevym
*/
#ifndef CHINING_H_
#define CHINING_H_
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef char* KeyType;
typedef char* ValueType;
typedef struct tagNode{
KeyType Key;
ValueType Value;
struct tagNode* Next;
}Node;
typedef Node* List;
typedef struct tagHashTable{
int TableSize;
List* Table;
} HashTable;
HashTable* CHT_CreateHashTable(int TableSize);
void CHT_DestroyHashTable(HashTable* HT);
Node* CHT_CreateNode(KeyType Key, ValueType Value);
void CHT_DestroyNode(Node* TheNode);
void CHT_Set(HashTable* HT, KeyType Key, ValueType Value);
ValueType CHT_Get(HashTable* HT, KeyType Key);
int CHT_Hash(KeyType Key, int KeyLength, int TableSize);
void CHT_DestroyHashTable(HashTable* HT);
void CHT_DestroyList(List L);
#endif /* 8_2_CHAINING_CHINING_H_ */
Chining.c
/*
* Chining.c
*
* Created on: 2019. 1. 7.
* Author: otrodevym
*/
#include "Chining.h"
HashTable* CHT_CreateHashTable(int TableSize) {
HashTable* HT = (HashTable*) malloc(sizeof(HashTable));
HT->Table = (List*) malloc(sizeof(List) * TableSize);
memset(HT->Table, 0, sizeof(List) * TableSize);
HT->TableSize = TableSize;
return HT;
}
Node* CHT_CreateNode(KeyType Key, ValueType Value) {
Node* NewNode = (Node*) malloc(sizeof(Node));
NewNode->Key = (char*) malloc(sizeof(char) * (strlen(Key) + 1));
strcpy(NewNode->Key, Key);
NewNode->Value = (char*)malloc(sizeof(char)* (strlen(Value)+1));
strcpy(NewNode->Value, Value);
NewNode->Next = NULL;
return NewNode;
}
void CHT_DestroyNode(Node* TheNode){
free(TheNode->Key);
free(TheNode->Value);
free(TheNode);
}
void CHT_Set(HashTable* HT, KeyType Key, ValueType Value){
int Address = CHT_Hash(Key, strlen(Key), HT->TableSize);
Node* NewNode = CHT_CreateNode(Key, Value);
if(HT->Table[Address] == NULL){
HT->Table[Address] = NewNode;
}else{
List L = HT->Table[Address];
NewNode->Next = L;
HT->Table[Address] = NewNode;
printf("Collision occured : Key(%s), Address(%d) \n", Key, Address);
}
}
ValueType CHT_Get(HashTable* HT, KeyType Key){
int Address = CHT_Hash(Key, strlen(Key), HT->TableSize);
List TheList = HT->Table[Address];
List Target = NULL;
if(TheList == NULL){
return NULL;
}
while(1){
if(strcmp(TheList->Key, Key) == 0 ){
Target = TheList;
break;
}
if(TheList->Next == NULL){
break;
}else{
TheList = TheList->Next;
}
}
return Target->Value;
}
void CHT_DestroyList(List L){
if(L == NULL){
return ;
}
if(L->Next != NULL){
CHT_DestroyList(L->Next);
}
CHT_DestroyNode(L);
}
void CHT_DestroyHashTable(HashTable* HT){
int i = 0;
for(i = 0; i < HT->TableSize; i++){
List L = HT->Table[i];
CHT_DestroyList(L);
}
free(HT->Table);
free(HT);
}
int CHT_Hash(KeyType Key, int KeyLength, int TableSize){
int i = 0;
int HashValue = 0;
for( i = 0; i < KeyLength; i++){
HashValue = (HashValue << 3) + Key[i];
}
HashValue = HashValue % TableSize;
return HashValue;
}
ChiningMain.c
/*
* ChiningMain.c
*
* Created on: 2019. 1. 7.
* Author: otrodevym
*/
#include "Chining.h"
int main(){
HashTable* HT = CHT_CreateHashTable(12289);
CHT_Set(HT, "MSFT", "Microsoft Corporation");
CHT_Set(HT, "JAVA", "Sun Microsystems");
CHT_Set(HT, "REDH", "Read Hat Linux");
CHT_Set(HT, "APAC", "Apach Org");
CHT_Set(HT, "ZYMZZ", "Unisys Ops Check");
CHT_Set(HT, "IBM", "IBM Ltd.");
CHT_Set(HT, "ORCL", "Oracle Corporation");
CHT_Set(HT, "CSCO", "Cisco Systems, Inc.");
CHT_Set(HT, "GOOG", "Google Inc.");
CHT_Set(HT, "YHOO", "Yahoo! Inc.");
CHT_Set(HT, "NOVL", "Novell, Inc.");
printf("\n");
printf("Key:%s, Value:%s \n", "MSFT", CHT_Get(HT, "MSFT"));
printf("Key:%s, Value:%s \n", "JAVA", CHT_Get(HT, "JAVA"));
printf("Key:%s, Value:%s \n", "REDH", CHT_Get(HT, "REDH"));
printf("Key:%s, Value:%s \n", "APAC", CHT_Get(HT, "APAC"));
printf("Key:%s, Value:%s \n", "ZYMZZ",CHT_Get(HT, "ZYMZ"));
printf("Key:%s, Value:%s \n", "IBM", CHT_Get(HT, "IBM"));
printf("Key:%s, Value:%s \n", "ORCL", CHT_Get(HT, "ORCL"));
printf("Key:%s, Value:%s \n", "CSCO", CHT_Get(HT, "CSCO"));
printf("Key:%s, Value:%s \n", "GOOG", CHT_Get(HT, "GOOG"));
printf("Key:%s, Value:%s \n", "YHOO", CHT_Get(HT, "YHOO"));
printf("Key:%s, Value:%s \n", "NOVL", CHT_Get(HT, "NOVL"));
CHT_DestroyHashTable(HT);
return 0;
}
OpenAddressing
OpenAddressing.h
/*
* OpenAddressing.h
*
* Created on: 2019. 1. 7.
* Author: otrodevym
*/
#ifndef OPENADDRESSING_H_
#define OPENADDRESSING_H_
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef char* KeyType;
typedef char* ValueType;
enum ElementStatus{
EMPTY = 0,
OCCUPIED = 1
};
typedef struct tagElementType{
KeyType Key;
ValueType Value;
enum ElementStatus Status;
}ElementType;
typedef struct tagHashTable{
int OccupiedCount;
int TableSize;
ElementType* Table;
} HashTable;
HashTable* OAHT_CreateHashTable(int TableSize);
void OAHT_DestroyHashTable(HashTable* HT);
void OAHT_ClearElement(ElementType* Elelment);
void OAHT_Set(HashTable** HT, KeyType Key, ValueType Value);
ValueType OAHT_Get(HashTable* HT, KeyType Key);
int OAHT_Hash(KeyType Key, int KeyLength, int TableSize);
int OAHT_Hash2(KeyType Key, int KeyLength, int TableSize);
void OAHT_Rehash(HashTable** HT);
#endif /* 8_3_OPEN_ADDRESSING_OPENADDRESSING_H_ */
OpenAddressing.c
/*
* OpenAddressing.c
*
* Created on: 2019. 1. 7.
* Author: otrodevym
*/
#include "OpenAddressing.h"
HashTable* OAHT_CreateHashTable(int TableSize){
HashTable* HT = (HashTable*)malloc(sizeof(HashTable));
HT->Table = (ElementType*)malloc(sizeof(ElementType) * TableSize);
memset(HT->Table, 0, sizeof(ElementType) * TableSize);
HT->TableSize = TableSize;
HT->OccupiedCount = 0;
return HT;
}
void OAHT_Set(HashTable** HT, KeyType Key, ValueType Value){
int KeyLen, Address, StepSize;
double Usage;
Usage = (double)(*HT)->OccupiedCount / (*HT)->TableSize;
if(Usage > 0.5){
OAHT_Rehash(HT);
}
KeyLen = strlen(Key);
Address = OAHT_Hash(Key, KeyLen, (*HT)->TableSize);
StepSize = OAHT_Hash2(Key, KeyLen, (*HT)->TableSize);
while((*HT)->Table[Address].Status != EMPTY && strcmp((*HT)->Table[Address].Key,Key) != 0){
printf("Collision occured! : Key(%s), Address(%d), StepSize(%d) \n", Key, Address, StepSize);
Address = (Address + StepSize) % (*HT)->TableSize;
}
(*HT)->Table[Address].Key = (char*)malloc(sizeof(char) * (strlen(Value)+1));
strcpy((*HT)->Table[Address].Key, Key);
(*HT)->Table[Address].Value = (char*)malloc(sizeof(char) * (KeyLen+1));
strcpy((*HT)->Table[Address].Value, Value);
(*HT)->Table[Address].Status = OCCUPIED;
(*HT)->OccupiedCount++;
printf("Key(%s) endtered at address(%d) \n", Key, Address);
}
ValueType OAHT_Get(HashTable* HT, KeyType Key){
int KeyLen = strlen(Key);
int Address = OAHT_Hash(Key, KeyLen, HT->TableSize);
int StepSize = OAHT_Hash2(Key, KeyLen, HT->TableSize);
while(HT->Table[Address].Status != EMPTY && strcmp(HT->Table[Address].Key, Key) != 0){
Address = (Address + StepSize) % HT->TableSize;
}
return HT->Table[Address].Value;
}
void OAHT_ClearElement(ElementType* Element){
if(Element->Status == EMPTY){
return ;
}
free(Element->Key);
free(Element->Value);
}
void OAHT_DestroyHashTable(HashTable* HT){
int i = 0;
for(i = 0; i < HT->TableSize; i++){
OAHT_ClearElement(&(HT->Table[i]));
}
free(HT->Table);
free(HT);
}
int OAHT_Hash(KeyType Key, int KeyLength, int TableSize){
int i = 0;
int HashValue = 0;
for(i = 0; i < KeyLength; i++){
HashValue = (HashValue << 3) + Key[i];
}
HashValue = HashValue % TableSize;
return HashValue;
}
int OAHT_Hash2(KeyType Key, int KeyLength, int TableSize){
int i = 0;
int HashValue = 0;
for(i = 0; i < KeyLength; i++){
HashValue = (HashValue << 3) + Key[i];
}
HashValue = HashValue % (TableSize - 3);
return HashValue +1;
}
void OAHT_Rehash(HashTable** HT){
int i = 0;
ElementType* OldTable = (*HT)->Table;
HashTable* NewHT = OAHT_CreateHashTable((*HT)->TableSize * 2);
printf("\n rehashed. New Table size is : %d \n" , NewHT->TableSize);
for(i = 0; i < (*HT)->TableSize; i++){
if(OldTable[i].Status == OCCUPIED){
OAHT_Set(&NewHT, OldTable[i].Key, OldTable[i].Value);
}
}
OAHT_DestroyHashTable((*HT));
(*HT) = NewHT;
}
OpenAddressingMain.c
/*
* OpenAddressingMain.c
*
* Created on: 2019. 1. 7.
* Author: otrodevym
*/
#include "OpenAddressing.h"
int main() {
HashTable* HT = OAHT_CreateHashTable(11);
OAHT_Set(&HT, "MSFT", "Microsoft Corporation");
OAHT_Set(&HT, "JAVA", "Sun Microsystems");
OAHT_Set(&HT, "REDH", "Read Hat Linux");
OAHT_Set(&HT, "APAC", "Apach Org");
OAHT_Set(&HT, "ZYMZZ", "Unisys Ops Check");
OAHT_Set(&HT, "IBM", "IBM Ltd.");
OAHT_Set(&HT, "ORCL", "Oracle Corporation");
OAHT_Set(&HT, "CSCO", "Cisco Systems, Inc.");
OAHT_Set(&HT, "GOOG", "Google Inc.");
OAHT_Set(&HT, "YHOO", "Yahoo! Inc.");
OAHT_Set(&HT, "NOVL", "Novell, Inc.");
printf("\n");
printf("Key:%s, Value:%s \n", "MSFT", OAHT_Get(HT, "MSFT"));
printf("Key:%s, Value:%s \n", "JAVA", OAHT_Get(HT, "JAVA"));
printf("Key:%s, Value:%s \n", "REDH", OAHT_Get(HT, "REDH"));
printf("Key:%s, Value:%s \n", "APAC", OAHT_Get(HT, "APAC"));
printf("Key:%s, Value:%s \n", "ZYMZZ", OAHT_Get(HT, "ZYMZ"));
printf("Key:%s, Value:%s \n", "IBM", OAHT_Get(HT, "IBM"));
printf("Key:%s, Value:%s \n", "ORCL", OAHT_Get(HT, "ORCL"));
printf("Key:%s, Value:%s \n", "CSCO", OAHT_Get(HT, "CSCO"));
printf("Key:%s, Value:%s \n", "GOOG", OAHT_Get(HT, "GOOG"));
printf("Key:%s, Value:%s \n", "YHOO", OAHT_Get(HT, "YHOO"));
printf("Key:%s, Value:%s \n", "NOVL", OAHT_Get(HT, "NOVL"));
OAHT_DestroyHashTable(HT);
return 0;
}
Java 소스
SimpleHashTable
SimpleHashTable.java
package h_hash_table;
public class SimpleHashTable {
private HashNode[] table;
private int size;
public SimpleHashTable() {
}
public SimpleHashTable(int size) {
this.table = new HashNode[size];
this.size = size;
}
private void shtSet(int key, int value) {
int address = this.shtHash(key);
this.table[address] = new HashNode();
this.table[address].setKey(key);
this.table[address].setValue(value);
}
private int shtGet(int key) {
int address = this.shtHash(key);
return this.table[address].getValue();
}
private int shtHash(int key) {
return key % this.size;
}
public static void main(String args[]) {
SimpleHashTable ht = new SimpleHashTable(193);
ht.shtSet(418, 32114);
ht.shtSet(9, 514);
ht.shtSet(27, 8917);
ht.shtSet(1031, 286);
System.out.println("418 : " + ht.shtGet(418));
System.out.println("9 : " + ht.shtGet(9));
System.out.println("27 : " + ht.shtGet(27));
System.out.println("1031 : " + ht.shtGet(1031));
String[] str= new String[10];
str[0] = "asdasd";
str[1] = "qweqwe";
str[2] = "zxczxc";
}
}
HashNode.java
package h_hash_table;
class HashNode{
private int key;
private int value;
public HashNode() {
}
public int getKey() {
return key;
}
public void setKey(int key) {
this.key = key;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
}
Chining
Chining.java
package h_hash_table;
public class Chining {
int size;
ChiningHashNode[] table;
public Chining() {
}
public Chining(int size) {
this.size = size;
this.table = new ChiningHashNode[size];
}
private ChiningHashNode chtCreateNode(String key, String value) {
ChiningHashNode chn = new ChiningHashNode();
chn.setKey(key);
chn.setValue(value);
chn.setNext(null);
return chn;
}
private void chtSet(String key, String value) {
int address = this.chtHash(key);
ChiningHashNode newNode = this.chtCreateNode(key, value);
if(this.table[address] == null) {
this.table[address] = new ChiningHashNode();
this.table[address] = newNode;
}else {
ChiningHashNode list = this.table[address];
newNode.setNext(list);
this.table[address] = newNode;
}
System.out.println("Collision occured : Key(" +key + "), Address(" + address + ")");
}
private String chtGet(String key) {
int address = this.chtHash(key);
ChiningHashNode list = this.table[address];
ChiningHashNode target = null;
if(list == null) {
return null;
}
while(true) {
if(list.getKey().equals(key)) {
target = list;
break;
}
if(list.getNext() == null) {
break;
}else {
list = list.getNext();
}
}
return target.getValue();
}
private int chtHash(String key) {
int hashValue = 0;
for(int i = 0; i < key.length(); i++) {
hashValue += key.charAt(i);
}
hashValue = hashValue % this.size;
return hashValue;
}
public static void main(String args[]) {
Chining c = new Chining(12289);
c.chtSet("MSFT", "Microsoft Corporation");
c.chtSet("JAVA", "Sun Microsystems");
c.chtSet("REDH", "Read Hat Linux");
c.chtSet("APAC", "Apach Org");
c.chtSet("ZYMZZ", "Unisys Ops Check");
c.chtSet("IBM", "IBM Ltd.");
c.chtSet("ORCL", "Oracle Corporation");
c.chtSet("CSCO", "Cisco Systems, Inc.");
c.chtSet("GOOG", "Google Inc.");
c.chtSet("YHOO", "Yahoo! Inc.");
c.chtSet("NOVL", "Novell, Inc.");
System.out.println("Key: MSFT, Value: " + c.chtGet("MSFT"));
System.out.println("Key: JAVA, Value: " + c.chtGet("JAVA"));
System.out.println("Key: REDH, Value: " + c.chtGet("REDH"));
System.out.println("Key: APAC, Value: " + c.chtGet("APAC"));
System.out.println("Key: ZYMZ, Value: " + c.chtGet("ZYMZ"));
System.out.println("Key: IBM, Value: " + c.chtGet("IBM"));
System.out.println("Key: ORCL, Value: " + c.chtGet("ORCL"));
System.out.println("Key: CSCO, Value: " + c.chtGet("CSCO"));
System.out.println("Key: GOOG, Value: " + c.chtGet("GOOG"));
System.out.println("Key: YHOO, Value: " + c.chtGet("YHOO"));
System.out.println("Key: NOVL, Value: " + c.chtGet("NOVL"));
}
}
ChiningHashNode.java
package h_hash_table;
public class ChiningHashNode {
String key;
String value;
ChiningHashNode next;
public ChiningHashNode() {
}
public String getKey() {
return key;
}
public void setKey(String key) {
this.key = key;
}
public String getValue() {
return value;
}
public void setValue(String value) {
this.value = value;
}
public ChiningHashNode getNext() {
return next;
}
public void setNext(ChiningHashNode next) {
this.next = next;
}
}
OpenAddressing
OpenAddressing.java
package h_hash_table;
enum ElementStatus{
EMPTY(0), OCCUPIED(1);
private int value;
private ElementStatus(int value) {
this.value = value;
}
}
public class OpenAddressing {
private int occupiedCount;
private int size;
private OAHashNode[] table;
class OAHashNode {
String key;
String value;
ElementStatus status;
public OAHashNode() {
}
public String getKey() {
return key;
}
public void setKey(String key) {
this.key = key;
}
public String getValue() {
return value;
}
public void setValue(String value) {
this.value = value;
}
public ElementStatus getStatus() {
return status;
}
public void setStatus(ElementStatus status) {
this.status = status;
}
}
public OpenAddressing() {
}
public OpenAddressing(int size) {
this.size = size;
this.table = new OAHashNode[size];
}
private void oahtSet(String key, String value) {
int address = 0;
int stepSize = 0;
double usage = (double)this.occupiedCount / this.size;
if(usage > 0.5) {
this.oahtRehash();
}
address = this.oahtHash(key);
stepSize = this.oahtHash2(key);
if(null == this.table[address] ||
(null == this.table[address].getStatus() || null ==this.table[address].getKey())) {
this.table[address] = new OAHashNode();
}else {
while(
this.table[address].getStatus() != ElementStatus.EMPTY
&& !this.table[address].getKey().equals(key)) {
System.out.println(
"Collision occured! : Key("+ key+"), Address("+ address +"), StepSize("+stepSize +")");
address = (address + stepSize) % this.size;
if(null == this.table[address]) {
this.table[address] = new OAHashNode();
break;
}
}
}
this.table[address].setKey(key);
this.table[address].setValue(value);
this.table[address].setStatus(ElementStatus.OCCUPIED);
this.occupiedCount++;
System.out.println("Key : " + key + " endtered at address : "+ address);
}
private String oahtGet(String key) {
int address = 0;
address=this.oahtHash(key);
int stepSize = 0;
stepSize = this.oahtHash2(key);
while(this.table[address].getStatus() != ElementStatus.EMPTY &&
!this.table[address].getKey().equals(key)) {
address = (address + stepSize) % this.size;
}
return this.table[address].getValue();
}
private int oahtHash(String key) {
int hashValue = 0;
for(int i =0; i < key.length(); i++) {
hashValue = (hashValue << 3) + key.charAt(i);
// hashValue += key.charAt(i);
}
hashValue = hashValue % this.size;
return hashValue;
}
private int oahtHash2(String key) {
int hashValue =0;
for(int i =0; i < key.length(); i++) {
hashValue = (hashValue << 3) + key.charAt(i);
// hashValue += key.charAt(i);
}
hashValue = hashValue % (this.size-3);
return hashValue+1;
}
private void oahtRehash() {
System.out.println("rehasing");
OAHashNode[] oa = this.table;
this.size = this.size *2;
this.occupiedCount = 0;
for(int i =0 ; i < this.size; i++) {
if(oa[i].getStatus() == ElementStatus.OCCUPIED) {
this.oahtSet(oa[i].getKey(), oa[i].getValue());
}
}
}
public static void main(String args[]) {
OpenAddressing oa = new OpenAddressing(12289);
oa.oahtSet("MSFT", "Microsoft Corporation");
oa.oahtSet("JAVA", "Sun Microsystems");
oa.oahtSet("REDH", "Read Hat Linux");
oa.oahtSet("APAC", "Apach Org");
oa.oahtSet("ZYMZZ", "Unisys Ops Check");
oa.oahtSet("IBM", "IBM Ltd.");
oa.oahtSet("ORCL", "Oracle Corporation");
oa.oahtSet("CSCO", "Cisco Systems, Inc.");
oa.oahtSet("GOOG", "Google Inc.");
oa.oahtSet("YHOO", "Yahoo! Inc.");
oa.oahtSet("NOVL", "Novell, Inc.");
System.out.println("Key: MSFT, Value: " + oa.oahtGet("MSFT"));
System.out.println("Key: JAVA, Value: " + oa.oahtGet("JAVA"));
System.out.println("Key: REDH, Value: " + oa.oahtGet("REDH"));
System.out.println("Key: APAC, Value: " + oa.oahtGet("APAC"));
System.out.println("Key: ZYMZ, Value: " + oa.oahtGet("ZYMZZ"));
System.out.println("Key: IBM, Value: " + oa.oahtGet("IBM"));
System.out.println("Key: ORCL, Value: " + oa.oahtGet("ORCL"));
System.out.println("Key: CSCO, Value: " + oa.oahtGet("CSCO"));
System.out.println("Key: GOOG, Value: " + oa.oahtGet("GOOG"));
System.out.println("Key: YHOO, Value: " + oa.oahtGet("YHOO"));
System.out.println("Key: NOVL, Value: " + oa.oahtGet("NOVL"));
}
}
반응형
'개발(합니다) > 컴퓨터 일반&CS' 카테고리의 다른 글
| [알고리즘]그래프(최소신장트리, 다익스트라) (0) | 2019.01.09 |
|---|---|
| [알고리즘]그래프(인접리스트, 깊이우선탐색, 너비우선탐색) (0) | 2019.01.08 |
| [알고리즘]우선순위 큐와 힙 (0) | 2019.01.07 |
| [알고리즘]탐색/검색(순차, 자기 구성, 이진 탐색, 레드블랙트리) (0) | 2019.01.05 |
| [알고리즘]정렬 알고리즘(버블, 삽입, 퀵) (0) | 2019.01.04 |
