열혈강의 자료구조 정리(해싱)

해싱은 검색키에 대한 산술 연산을 이용한 검색 방식임

검색 키 값을 입력값으로 계산을 실시하면 검색하려는 자료의 위치를 알 수 있다는 것이 기본 개념

검색키 -> 해싱함수 -> 검색 자료의 주소를 -> 해시테이블에서 찾음

그런데 계산된 주소에 다른 자료가 저장되어 있다면 충돌이 발생한다.

 

해싱함수로 사용될 수 있는 방법

1. 나머지 함수

가장 일반적임 검색 키 값 k를 해시 테이블의 크기 m으로 나눈 나머지를 해시 주소로 사용

2. 접기함수

검색 키의 크기가 해시 테이블의 크기보다 큰 정수일 경우 사용

검색 키 값 k가 데이블의 크기 m보다 큰 경우 k를 m의 자릿수와 같은 크기로 분할한 후 분할된 부분들을 이용하여 해시 테이블 주소 만듬

예)

검색 키값 : 1234512345(10자리)

해시 테이블 크기 m : 999(3자리)

123 451 234 5로 분할 후

다 더하면 813나옴(값)

3. 경계접기 함수

위의 접기함수와 같으나 키값을 나누고

123 451 234 5

이럴때 123와 234를 뒤집어 더한다 321 432로

그리고 초과하는 자릿수(1000단위) 버림

4. 중간제곱함수

검색 키를 제곱한 값 중에서 중간 부분을 해시 테이블 주소로 이용하는 방법

검색 키 값 9451

9451 * 9451 = 89321401

여기서 중간부분 4자리를 이용하여 3214 사용

5. 숫자분석방법

숫자로 이뤄진 검색 키 값의 각 자릿수의 분포를 미리 분석하여 해시 주소로 사용하는 방법

즉, 검색 키 값의 각 자릿수 중에서 가장 편중된 분산을 가지는(충돌 발생 가능성이 큰) 자릿수를 생략하고 가장 고르게 분포된(출동 가능성 낮은) 자릿수만을 추출하여 이를 주소로 활용

예) 검색 키 값 : 학생의 학번 2010-9025

단, 처음 4자리 입학연도

다음 2자리 학과번호

마지막 2자리 같은 학과내 학생고유 번호

다 더하면 9025 주소값 사용

 

*문자열의 경우 문자의 고유값(A는 65이런것.)이 있으므로 그걸 활용함..

 

해싱함수를 잘 선택하여 충돌을 최소화하지만 충돌이 발생했다면 어떻게 해야할까..

군집화(특정 주소들 주위로 뭉치는것)현상이 높게 발생하면 안좋음..그래서 최소화 설계해야함..

이러한 해결방법중

1. 충돌이 일어난 키 값을 다른 비어 있는 주소를 찾아 저장하는 개방주소(open addressing) 기법

(모든 주소가 찬 경우에는 안되며 주소를 찾을때까지 반복함)

2. 해싱 테이블의 구조 자체는 변경하는 체이닝(chaining) 기법

 

 

개방 주소법에는

1) 선형 조사법 2) 제곱 조사법 3) 이중 해싱 등이 있다.

 

1) 선형 조사법 : 충돌이 발생할 경우 주소를 일정한 상수만큼 증가시켜 다시 조사하는 방법

: 충돌한 주소를 시작으로 차례로 저장되기 때문에 군집화 현상이 발생할 가능성이 크다.

예를 들어

해시 테이블 크기 : 5

해싱함수 : 나머지 함수(mod 5)

저장되는 검색 키 값 : 1,3,8,13

일경우에 해시 테이블에 주소는 해싱함수에 의해서 계산되는데..3, 8, 13이 동일하게 충돌된다

3mod 5 = 3, 8 mod 5 = 3, 13 mod 5 = 3

검색 키값을 순서대로 저장한다면 키값 1,3이 해싱함수에 의해 1,3주소에 저장되고

키값 8가 해싱함수에 의해 주소가 3이 나오고 3이 있으므로 충돌되어 주소에 1증가(이때 증가는 키값에 증가시키는것이다) 주소 4에 저장됨..

그리고 13도 마찬가지 3에 있고 4에 있고 5에 들어감(근데 크기가 5이니 0으로 들어가겠지..01234)

 

2) 제곱 조사법 : 충돌이 발생한 경우 주소를 조사 횟수의 제곱만큼 증가시켜 다시 조사

1차 충돌에서는 1더하고 2차에서는 2*2 4를 n번째는 n^2을 주소에 더함.

 

3) 이중해싱 : 충돌이 발생할 경우 주소를 원래의 해싱 함수와는 다른 추가적인 해싱함수를 이용해 주소를 증가시켜 다시 조사

여러가지 방법이 있으나 가장 간단한 방법으로 조사간격을 이용하는것.

조사간격 = M - (k mod M) //M은 해시 테이블 크기 k는 검색 키

예를 들어

위으 해시 테이블 등 상황은 똑같고

8번 키값 해싱함수시 3주소로 충돌발생

조사간격 = M - (k mod M) = 5 - (8 mod 5) = 5 - 3 = 2

이번 충돌한 주소 = 3

새로운 주소는 : 3 + 2 mod 5 = 0

이런식임..

이중 해싱은 2차 집중까지 줄어드는 장점이 있음.

 

아래예제는

첫번째 충돌 해결방법 : 개방주소

1) 나머지 함수로 구현된 해싱함수 2) 호너의 방법으로 키값을 정수로 변환 3) 선형 조사법으로 계산된 충돌처리

이렇게 구현했다..

해쉬element에는 해쉬상태와 값 그리고 키값(문자열)이 들어가고

해쉬 테이블에서 element를 버킷사이즈를 활용해서 new받고 사이즈 확보하고...

 

}

const int HASH_KEY_SIZE = 30;

class HashElement
{
public:
 enum HashElementStatus
 {
  e_EMPTY = 0,
  e_USED,
  e_DELETED //사용되었다 삭제된 상태
 };
public:
 int GetValue()
 {
  return nValue;
 }
 
 HashElementStatus eStatus;
 char ckey[HASH_KEY_SIZE + 1];
 int nValue;

public:
 HashElement(char *key="", int value=0) : eStatus(e_EMPTY), nValue(value)
 {
  strcpy_s(ckey, key);
  cout << "저장키값" << ckey <<" " << "저장수치" << nValue << endl;
 }
 ~HashElement() {}
};

class HashTable
{
public:
 int nBucketSize;
 int nCurrentElementCount;
 HashElement  *pElement;
public:
 HashTable(int bucketSize=0); //초기화 및 메모리 할당
 ~HashTable();
 bool addElementSHT(HashElement element); //새로운 자료저장함수
 int hashFunction(char *pKey); //해쉬함수 나머지 연산
 unsigned int stringToInt(char *pKey); //호너의 방법
 bool isEmptyOrDeleteBudcket(int numkey); //해당 버킷의 상태 확인
 HashElement* searchHT(char *pKey); //자료 검색
 bool isEmptyBucket(int numkey);

 void DisplayHashTable();
};

HashTable::HashTable(int bucketSize) : nBucketSize(bucketSize), pElement(nullptr)
{
 if (bucketSize == 0)
 {
  //에러처리
 }
 cout << "해시 테이블 생성 : 사이즈" << nBucketSize << endl;
 pElement = new HashElement[bucketSize];
}

HashTable::~HashTable()
{
 delete [] pElement;
}

bool HashTable::addElementSHT(HashElement element)
{
 bool ret = false;
 int bucketIndex = 0;
 int tempIndex = 0;
 int inc = 1;

 bucketIndex = hashFunction(element.ckey); //키값 확인
 if (bucketIndex < 0 || bucketIndex >= nBucketSize)
 {
  cout << "잘못된 해쉬 테이블 주소가 계산되었습니다" << endl;
  return ret;
 }

 tempIndex = bucketIndex;
 do
 {
  //만약 빈 버킷 혹은 삭제된 버킷인 경우
  if (isEmptyOrDeleteBudcket(tempIndex))
  {
   pElement[tempIndex] = element;
   pElement[tempIndex].eStatus = HashElement::e_USED;
   ret = true;
   break;
  }
  else
  {
   //현재 주소에 검색 키와 동일한 키를 가지는 경우
   if (strcmp(pElement->ckey, element.ckey) == 0)
   {
    cout << "오류 중복된 키" << element.ckey << endl;
    ret = false;
    break;
   }
   //현재 주소에 검색키와 다른 키를 가진 자료가 저장된 경우(충돌)
   else
   {
    tempIndex = (tempIndex + inc) % nBucketSize; //선형조사법에 따른 충돌처리
    if (tempIndex == bucketIndex) //새로구해진 버킷의 주소 tempindex가 처음계산된 주소 bucketindex와 같다면 꽉참..돌고돌아
    {
     cout << "해쉬 테이블이 가득찼습니다" << endl;
     ret = false;
     break;
    }
   }
  }
 } while (tempIndex != bucketIndex);
 return ret;
}

int HashTable::hashFunction(char *pKey)
{
 int key = 0;
 unsigned int temp_key = 0;
 if (pKey == NULL)
 {
  cout << "키값없음" << endl;
  return key;
 }
 temp_key = stringToInt(pKey);
 if (nBucketSize > 0)
 {
  key = temp_key%nBucketSize; //나머지 연산으로 주소계산
 }
 return key;
}

unsigned int HashTable::stringToInt(char *pKey)
{
 unsigned int ret = 0;
 while (*pKey != '\0')
 {
  ret = (ret * 31) + (*pKey);
  *pKey++;
 }
 return ret;
}

bool HashTable::isEmptyOrDeleteBudcket(int numkey)
{
 bool ret = false;
 if (pElement != NULL)
 {
  if (pElement[numkey].eStatus == HashElement::e_EMPTY || pElement[numkey].eStatus == HashElement::e_DELETED)
  {
   ret = true;
  }
 }
 return ret;
}

HashElement* HashTable::searchHT(char *pKey)
{
 HashElement *temp = nullptr;
 int bucketindex = 0;
 int tempindex = 0;
 int inc = 1;
 if (pElement == nullptr)
 {
  cout << "Null 해시 테이블" << endl;
  return nullptr;
 }
 bucketindex = hashFunction(pKey);
 if (bucketindex < 0)
 {
  cout << "오류 잘못된 해쉬 테이블 주소가 계산됨" << endl;
  return nullptr;
 }

 tempindex = bucketindex;
 do
 {
  if (isEmptyBucket(tempindex))
  {
   cout << "검색실패 검색키" << tempindex << "에 값이 존재 하지 않습니다" << endl;
   break;
  }

  else
  {
   if (pElement[tempindex].eStatus == HashElement::e_USED && strcmp(pElement[tempindex].ckey, pKey) == 0)
   {
    temp = &pElement[tempindex];
    break;
   }
   else
   {
    tempindex = (tempindex + 1) % nBucketSize;
    if (tempindex == bucketindex)
    {
     cout << "검색실패 존재하지 않음" << endl;
     break;
    }
   }
  }
 } while (tempindex != bucketindex);
 return temp;
}

bool HashTable::isEmptyBucket(int numkey)
{
 bool ret = false;
 if (pElement != nullptr)
 {
  if (pElement[numkey].eStatus == HashElement::e_EMPTY)
  {
   ret = true;
  }
 }
 return ret;
}

void HashTable::DisplayHashTable()
{
 for (int i = 0; i < nBucketSize; i++)
 {
  cout << i << "번째" << pElement[i].ckey << " " << pElement[i].nValue <<" " << "키값" << hashFunction(pElement[i].ckey) << endl;
 }
}

int main()
{
 HashTable Pt(8);
 cout << endl;
 HashElement e1("january", 1);
 HashElement e2("february", 2);
 HashElement e3("march", 3);
 HashElement e4("april", 4);
 HashElement e5("may", 5);
 HashElement e6("june", 6);
 HashElement e7("july", 7);
 

 Pt.addElementSHT(e1);
 Pt.addElementSHT(e2);
 Pt.addElementSHT(e3);
 Pt.addElementSHT(e4);
 Pt.addElementSHT(e5);
 Pt.addElementSHT(e6);
 Pt.addElementSHT(e7);
 
 cout << endl;
 
 cout << "해시 테이블 내용" << endl;
 cout << endl;

 Pt.DisplayHashTable();

 HashElement *p = nullptr;

 cout << endl;
 //p = Pt.searchHT("december");
 p = Pt.searchHT("may");
 cout << "검색키 " << p->ckey << "검색결과 " << p->nValue << endl;

 _getch();
 return 0;
}

결과랑 사용하기에는 매우 힘들지만..아무튼 손봐야함.. 삭제구현없음..

 

두번째 충돌 해결방법 : 체이닝

해시테이블의 구조를 변경하여 각 주소에 하나 이상의 검색 키 값이 저장될 수 있도록 하는 방법..(연결리스트 활용이라 이거고..충돌이 발생할 때 동적으로 여러개의 검색 키 값을 저장할 수 있게 하는 방법)

* 근데 연결리스트에 저장할때 무조건 앞? 뒤? 키값에 의한 정렬? 등을 선택해야함..

충돌만 틀릴뿐 해싱함수에 의한 선형조사법은 마찬가지로 같음..

 

아래소스는 1) 해싱함수로 나머지 함수 2) 검색키가 문자열 호너의 방법 3) 충돌 해결법으로 체이닝 사용

위와는 다르게 STL vector와 list를 활용함. 키값은 string 문자열을 이용하여..

삭제는 안만듬..

하면서 문제가 발생되었던것..

STL의 find함수를 특정 객체나 클래스의 멤버를 찾기위해서 사용한다면 해당 객체의 oprator== 구현해서 하면된다는것.?

그러고 typedef 쓸모 있다는거..마지막으로 없는값 검색에서 어디가 오류나는지 알고 싶지 않다는거..ㅜ

using namespace std;

const int HASH_KEY_SIZE = 10;

class HashElement
{
public:
 string mKey;
 int mValue;
public:
 HashElement(string key="", int num = 0);
 ~HashElement();
 friend bool operator==(const HashElement &n1, const HashElement &n2);
};

bool operator==(const HashElement &n1, const HashElement &n2)
{
 return n1.mKey == n2.mKey;
}

HashElement::HashElement(string key, int num) : mValue(num), mKey(key)
{
 
}

HashElement::~HashElement()
{}

typedef list<HashElement> HashList;
typedef vector<HashList> Hash;

//HASHTABLE
class HashTable
{
public:
 int mBucketSize;
 int mCurrentElementCount;
 Hash vElement;
public:
 HashTable(int num = 10);
 ~HashTable();
 int hashFunction(string pKey);
 unsigned int stringToInt(string pKey);
 bool addSHT(HashElement element);
 HashElement searchHT(string pKey);
 HashList* searchBucket(string pKey);

 void displayHashTable();
};

HashTable::HashTable(int num) : mBucketSize(num), mCurrentElementCount(0), vElement(mBucketSize)
{
 cout << "HashTable 생성" << endl;
}

HashTable::~HashTable()
{
 cout << "HaslTable 소멸자" << endl;
}

int HashTable::hashFunction(string pKey)
{
 int key = 0;
 unsigned int temp_key = 0;
 if (pKey.empty())
 {
  cout << "키값없음" << endl;
  return key;
 }
 temp_key = stringToInt(pKey);
 if (mBucketSize > 0)
 {
  key = temp_key%mBucketSize; //나머지 연산으로 주소계산
 }
 return key;
}

unsigned int HashTable::stringToInt(string pKey)
{
 unsigned int ret = 0;
 const char *temp = pKey.c_str();
 temp=const_cast<char*>(temp); //위험한짓..
 while (*temp != '\0')
 {
  ret = (ret * 31) + (*temp);
  *temp++;
 }
 return ret;
}

bool HashTable::addSHT(HashElement element)
{
 bool ret = false;

 int bucketIndex = 0;
 bucketIndex = hashFunction(element.mKey);
 if (bucketIndex >= 0)
 {
  vElement[bucketIndex].push_back(element);
  mCurrentElementCount++;
  ret = true;
  cout << "저장키값" << bucketIndex << "으로 해쉬 테이블 추가성공" << endl;
 }
 else
 {
  cout << "해쉬 테이블계산이 잘못되었습니다" << endl;
 }
 return ret;
}

HashElement HashTable::searchHT(string pKey)
{
 HashList* list = searchBucket(pKey);
 HashList::iterator iter;
 iter = find(list->begin(), list->end(), HashElement(pKey));
 if (iter != list->end())
 {
  cout << iter->mKey.c_str() << " " << "를 찾았습니다" << endl;
  return *iter;
 }
 else
 {
  cout << "찾지 못했습니다" << endl;
 }

}

 HashList* HashTable::searchBucket(string pKey)
{
 HashList* temp = nullptr;
 int bucketIndex = 0;
 bucketIndex = hashFunction(pKey);
 if (bucketIndex >= 0)
 {
  cout << bucketIndex << "테이블의 주소를 반환합니다." << endl;
  temp = &vElement[bucketIndex];
 }
 else
 {
  cout << "오류 잘못된 해쉬 테이블 주소가 계산되었습니다." << endl;
 }
 return temp;
}

 void HashTable::displayHashTable()
 {
  Hash::iterator iter1;
  HashList::iterator iter2;
  int position = 0;
  for (iter1 = vElement.begin(); iter1 != vElement.end(); iter1++)
  {
   for (iter2 = vElement[position].begin(); iter2 != vElement[position].end(); iter2++)
   {
    cout << position << "번째 자료" << " " << "저장된 문자열" << iter2->mKey << " " << "저장된 값" << iter2->mValue << endl;
   }
   ++position;
  }
 }

int main()
{
 HashTable a;
 HashElement f("eeeeee", 5);
 HashElement b("aa", 1);
 HashElement g("ffff", 6);
 HashElement c("bbb", 2);
 HashElement d("cccc", 3);
 HashElement e("ddddd", 4);
 HashElement h("ggg", 7);

 a.addSHT(b);
 a.addSHT(c);
 a.addSHT(d);
 a.addSHT(e);
 a.addSHT(f);
 a.addSHT(g);
 a.addSHT(h);

 a.displayHashTable();
 _getch();
 return 0;
}