Hash Map

시퀀스 컨테이너와 연관 컨테이너 시퀀스 컨테이너 -vector, list, deque 등 - 보관할 자료의 양이 많지 않고, - 검색이 중요하지 않은 경우 연관 컨테이너 -map, set, hash_map, hash_set -Key 와 짝을 이루어 자료 보관 - 대량의 자료를 보관하고 - 빠른 검색이 필요한 경우

Hash table / Hash map In computer science, a hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys (e.g., a person's name), to their associated values(e.g., their telephone number).computer sciencedata structurehash functionkeysvalues Thus, a hash table implements an associative array. The hash function is used to transform the key into the index (the hash) of an array element (the slot orbucket) where the corresponding value is to be sought.associative arrayarray Wikipedia.org map, set : 자료를 정렬하여 저장 hash_map, hash_set : 자료를 정렬하지 않고 저장

Hash_map 의 자료구조 Key 값 해시함수 버킷 번호 슬롯 1 슬롯 2 슬롯 … n Hash table

Hash_map 사용 1. 많은 자료를 저장하고, 검색속도가 빨라야 한다. 2. 너무 빈번하게 자료를 삽입, 삭제하지 않는다. #include using namespace stdext; hash_map 선언 hash_map 변수 이름 hash_map 선언 예 hash_map hash1; 동적 할당 hash_map * 변수 이름 = new hash_map ; hash_map * hash1 = new hash_map ;

Hash_map 의 주요 멤버 멤버설명 begin 첫 번째 원소의 랜덤 접근 반복자를 반환 clear 저장한 모든 원소를 삭제 empty 저장한 요소가 없으면 true 반환 end 마지막 원소 다음의 ( 미 사용 영역 ) 반복자를 반환 erase 특정 위치의 원소나 지정 범위의 원소들을 삭제 find Key 와 연관된 원소의 반복자 반환 insert 원소 추가 lower_bound 지정한 Key 의 요소가 있다면 해당 위치의 반복자를 반환 rbegin 역방향으로 첫 번째 원소의 반복자를 반환 rend 역방향으로 마지막 원소 다음의 반복자를 반환 size 원소의 개수를 반환 upper_bound 지정한 Key 요소가 있다면 해당 위치 다음 위치의 반복자 반환

hash_map 사용 예 – 유저 관리 #include #include using namespace std; using namespace stdext; struct GameCharacter // 게임 캐릭터 { int _CharCd; // 캐릭터 코드 int _Level; // 레벨 int _Money; // 돈 GameCharacter() { } GameCharacter( int CharCd, int Level, int Money ){ _CharCd = CharCd; _Level = Level; _Money = Money; } }; void main() { hash_map Characters; GameCharacter Character1(12, 7, 1000 ); Characters.insert(hash_map ::value_type(12, Character1)); GameCharacter Character2(15, 20, ); Characters.insert(hash_map ::value_type(15, Character2)); GameCharacter Character3(200, 34, ); Characters.insert(hash_map ::value_type(200, Character3)); // iterator 와 begin, end 사용. 저장한 요소를 정방향으로 순회 hash_map ::iterator Iter1; for( Iter1 = Characters.begin(); Iter1 != Characters.end(); ++Iter1 ) { cout second._CharCd second._Level second._Money << endl; } cout << endl; // rbegin, rend 사용. 저장한 요소의 역방향으로순회 hash_map ::reverse_iterator RIter; for( RIter = Characters.rbegin(); RIter != Characters.rend(); ++RIter ) { cout second._CharCd second._Level second._Money << endl; } cout << endl << endl; // Characters 에 저장한 요소 수 int CharacterCount = Characters.size(); // 검색. 캐릭터 코드 15 인 캐릭터를 찾는다. hash_map ::iterator FindIter = Characters.find(15); // 찾지 못했다면 FindIter 은 end 위치의 반복자가 반환된다. if( Characters.end() == FindIter ) { cout second._CharCd second._Level second._Money << endl; } cout << endl; for( Iter1 = Characters.begin(); Iter1 != Characters.end(); ++Iter1 ) { cout second._CharCd second._Level second._Money << endl; } cout << endl << endl; // 삭제 / 캐릭터 코드가 15 인 캐릭터를 삭제한다. Characters.erase( 15 ); for( Iter1 = Characters.begin(); Iter1 != Characters.end(); ++Iter1 ) { cout second._CharCd second._Level second._Money << endl; } cout << endl << endl; // 모든 캐릭터를 삭제한다. Characters.erase( Characters.begin(), Characters.end() ); // Characters 공백 조사 if( Characters.empty() ) { cout << "Characters 는 비어 있습니다." << endl; } }

hash_map 사용 예 – 유저 관리

Map

map 의 자료구조 루트노드 부모노드 자식노드

map 의 사용 사용 조건 1. 정렬해야 한다. 2. 많은 자료를 저장하고, 검색이 빨라야 한다. 3. 빈번하게 삽입, 삭제하지 않는다. #include 변수선언 map 변수 이름 map map1; - 기본적으로 Key 를 대상으로 오름차순 정렬 함수객체를 사용한 정렬 map 변수 이름 - 내림차순 정렬 map > map1;

map 의 주요 멤버 멤버멤버설명 begin 첫 번째 원소의 랜덤 접근 반복자를 반환 clear 저장하고 있는 모든 원소를 삭제 empty 저장 하고 있는 요소가 없으면 true 반환 End 마지막 원소 다음의 ( 미 사용 영역 ) 반복자를 반환 erase 특정 위치의 원소나 지정 범위의 원소들을 삭제 Find key 와 연관된 원소의 반복자 반환 insert 원소 추가 lower_bound 지정한 key 의 요소를 가지고 있다면 해당 위치의 반복자를 반환 operator[] 지정한 key 값으로 원소 추가 및 접근 rbegin 역방향으로 첫 번째 원소의 반복자를 반환 rend 역방향으로 마지막 원소 다음의 반복자를 반환 size 원소의 개수를 반환 upper_bound 지정한 key 요소를 가지고 있다면 해당 위치 다음 위치의 반복자 반환

map 사용 예 – 아이템 리스트 출력 #include #include #include using namespace std; struct Item { char Name[32]; // 이름 char Kind; // 종류 int BuyMoney; // 구입 가격 int SkillCd; // 스킬 코드 }; int main() { map Items; map ::iterator IterPos; typedef pair ItemPair; Item Item1; strncpy( Item1.Name, " 긴칼 ", 32 ); Item1.Kind = 1; Item1.BuyMoney = 200; Item1.SkillCd = 0; Item Item2; strncpy( Item2.Name, " 성스러운 방패 ", 32 ); Item2.Kind = 2; Item2.BuyMoney = 1000; Item2.SkillCd = 4; Item Item3; strncpy( Item3.Name, " 해머 ", 32 ); Item3.Kind = 1; Item3.BuyMoney = 500; Item3.SkillCd = 0; // Items 에 아이템 추가 Items.insert( map ::value_type(Item2.Name, Item2) ); Items.insert( ItemPair(Item1.Name, Item1) ); // Items 가 비어 있지 않다면 if( false == Items.empty() ){ cout << " 저장된 아이템 개수 - " << Items.size() << endl; } for( IterPos = Items.begin(); IterPos != Items.end(); ++IterPos ) { cout first second.BuyMoney << endl; } IterPos = Items.find(" 긴칼 "); if( IterPos == Items.end() ) { cout > Items2; map >::iterator IterPos2; Items2.insert( map ::value_type(Item2.Name, Item2) ); Items2.insert( ItemPair(Item1.Name, Item1) ); // operator[] 를 사용하여 저장 Items2[Item3.Name] = Item3; for( IterPos2 = Items2.begin(); IterPos2 != Items2.end(); ++IterPos2 ) { cout first second.BuyMoney << endl; } cout << endl; cout second.BuyMoney << endl; } else { cout << " 해머는 없습니다 " << endl; } cout << endl; // 아이템 " 긴칼 " 을 삭제한다. IterPos2 = Items2.find(" 긴칼 "); if( IterPos2 != Items2.end() ) { Items2.erase( IterPos2 ); } cout << "Items2 에 있는 아이템 개수 : " << Items2.size() << endl; return 0; }

map 사용 예 – 아이템 리스트 출력