Map
- key - value 쌍의 자료구조
- 어떻게 동작할까?
ES6: Map object must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements in the collection.
- 상수 시간복잡도를 갖는 해시 테이블 또는 다른 메카니즘으로 구현
Node의 경우
- 21.6.1(release)
- V8(11.8.172.17)
// v8/src/objects/js-collection.h
// The JSMap describes EcmaScript Harmony maps
class JSMap : public TorqueGeneratedJSMap<JSMap, JSCollection> {
public:
static void Initialize(Handle<JSMap> map, Isolate* isolate);
static void Clear(Isolate* isolate, Handle<JSMap> map);
void Rehash(Isolate* isolate);
// Dispatched behavior.
DECL_PRINTER(JSMap)
DECL_VERIFIER(JSMap)
TQ_OBJECT_CONSTRUCTORS(JSMap)
};Rehash함수를 보아 해시 테이블을 사용한 것을 알 수 있습니다.
OrderedHashMap
- deterministic hash tables 알고리즘을 구현한 컨테이너
- 각 항목은 힙에서 별도로 할당 X
- 삽입 순서로 dataTable에 저장
- Cpp의 unordered_map 과 대조
- 삭제 시 체인은 건드리지 않고 키의 값만 수정
구조
- Entry : 저장 단위
- key: 키
- Valeu: valeu
- chain: 다음 요소의 주소 (체이닝에 사용)
- CloseTable : 해시 테이블
- hashTable: 버킷 주소
- dataTable: Entry가 저장되는 곳
struct Entry {
Key key;
Value value;
Entry *chain;
}
class CloseTable {
Entry*[] hashTable; // array of pointers into the data table
Entry[] dataTable;
}삽입
- 삽입된 순서로 dataTable에 저장
- Map의 순회는 결정적이게 됨
- 해시 함수: modulo 2
- 삽입 순서: 1, 2, 3, 4
closeTable : {
hashTblae: [4, 3], // key 가라키는 주소
dataTable: [
{
// bucket: 1, key로 계산하여 산출하기 때문에 주석 처리
key: 1,
value: "1",
chain: -1,
},
{
// bucket: 0,
key: 2,
value: "2",
chain: -1,
},
{
// bucket: 1,
key: 3,
value: "3",
chain: 1,
},
{
// bucket: 0,
key: 4,
value: "4",
chain: 2,
},
],
live_element_size: 4,
deleted_element_size: 0
}크기 초과 시
- 초기값
- 버킷 크기 = 2
- capacity = 4 = 2 * 버킷 크기
- capacity 가 다 차면 + 삭제된 요소가 절반 미만이면
- 버킷 크기 * 2
- capctiy 가 다 차면 + 삭제 요소 절반 이상
- 삭제 요소 삭제 (ㅋㅋ)
- 테이블 재할당
- 리해싱
삭제
- 체인은 건드리지 않고 키 값 수정
- 삭제 순서: 1, 2
closeTable : {
hashTblae: [4, 3],
dataTable: [
{
// bucket: 1,
key: 1,
value: "1",
chain: -1,
},
{
// bucket: 2,
key: 2,
value: "2",
chain: -1,
},
{
// bucket: 3,
key: 3,
value: "3",
chain: 1,
},
{
// bucket: 1,
key: 4,
value: "4",
chain: 2,
},
],
live_element_size: 2,
deleted_element_size: 2
}참고용 코드
- 알고리즘
void CloseTable::set(KeyArg key, ValueArg value) { // 1. 주어진 키의 해시값 계산 hashcode_t h = hash(key); // 2. 키를 이용하여 해시 테이블에서 해당 키의 엔트리 찾기 Entry *e = lookup(key, h); // 3. 찾은 엔트리가 존재하면 값을 업데이트하고 종료 if (e) { e->value = value; } else { // 4. 찾은 엔트리가 없으면 새 엔트리를 추가 if (entries_length == entries_capacity) { // 5. 테이블의 삭제된 엔트리가 1/4 이상이면 재해시, 아니면 테이블 확장 rehash(live_count >= entries_capacity * 0.75 ? (table_mask << 1) | 1 : table_mask); } // 6. 해시값을 현재 테이블 크기에 맞게 조정 h &= table_mask; // 7. 새로운 엔트리 생성 및 초기화 live_count++; e = &entries[entries_length++]; e->key = key; e->value = value; e->chain = table[h]; // 8. 새로운 엔트리를 해시 테이블에 추가 table[h] = e; } } bool CloseTable::remove(KeyArg key) { // 1. 주어진 키를 이용하여 엔트리 찾기 Entry *e = lookup(key, hash(key)); // 2. 찾은 엔트리가 없으면 false 반환 if (e == NULL) return false; // 3. 찾은 엔트리가 있으면 엔트리 제거 및 빈 엔트리로 만들기 live_count--; makeEmpty(e->key); // key = 0 // 4. 삭제된 엔트리가 많으면 테이블 축소 if (table_mask > initial_buckets() && live_count < entries_length * min_vector_fill()) rehash(table_mask >> 1); // 5. 성공적으로 엔트리 제거되었음을 반환 return true; } void CloseTable::rehash(size_t new_table_mask) { // 1. 새로운 테이블 용량 계산 size_t new_capacity = size_t((new_table_mask + 1) * fill_factor()); // 2. 새로운 해시 테이블 및 새로운 엔트리 배열 생성 EntryPtr *new_table = new EntryPtr[new_table_mask + 1]; memset(new_table, 0, (new_table_mask + 1) * sizeof(EntryPtr)); Entry *new_entries = new Entry[new_capacity]; // 3. 기존 엔트리를 새로운 엔트리 배열로 이동 Entry *q = new_entries; for (Entry *p = entries, *end = entries + entries_length; p != end; p++) { if (!isEmpty(p->key)) { hashcode_t h = hash(p->key) & new_table_mask; q->key = p->key; q->value = p->value; q->chain = new_table[h]; new_table[h] = q; q++; } } // 4. 기존 테이블 및 엔트리 배열 삭제 및 새로운 테이블 및 엔트리 배열로 교체 delete[] table; delete[] entries; table = new_table; table_mask = new_table_mask; entries = new_entries; entries_capacity = new_capacity; entries_length = live_count; } - V8
MaybeHandle<OrderedHashSet> OrderedHashSet::Add(Isolate* isolate, Handle<OrderedHashSet> table, Handle<Object> key) { // 1. 해시값 계산 및 중복 체크를 위해 GC 비활성화 int hash; { DisallowGarbageCollection no_gc; Tagged<Object> raw_key = *key; Tagged<OrderedHashSet> raw_table = *table; // 키의 해시값 계산 또는 기존 해시값 가져오기 hash = Object::GetOrCreateHash(raw_key, isolate).value(); // 테이블에 이미 버킷이 있는 경우 중복 체크 수행 if (raw_table->NumberOfElements() > 0) { int raw_entry = raw_table->HashToEntryRaw(hash); // 버킷 체인을 따라가며 중복된 키가 있는지 확인 while (raw_entry != kNotFound) { Tagged<Object> candidate_key = raw_table->KeyAt(InternalIndex(raw_entry)); // 이미 존재하는 키라면 추가하지 않고 현재 테이블 반환 if (Object::SameValueZero(candidate_key, raw_key)) return table; raw_entry = raw_table->NextChainEntryRaw(raw_entry); } } } // 2. 테이블 용량 조절을 위해 GC 비활성화 MaybeHandle<OrderedHashSet> table_candidate = OrderedHashSet::EnsureCapacityForAdding(isolate, table); // 용량 조절에 실패한 경우 예외 처리 if (!table_candidate.ToHandle(&table)) { CHECK(isolate->has_pending_exception()); return table_candidate; } // 3. GC 비활성화 및 테이블 수정을 위해 원시 테이블 가져오기 DisallowGarbageCollection no_gc; Tagged<OrderedHashSet> raw_table = *table; // 기존 버킷 값 및 엔트리 정보 읽기 int bucket = raw_table->HashToBucket(hash); int previous_entry = raw_table->HashToEntryRaw(hash); int nof = raw_table->NumberOfElements(); // 4. 새로운 엔트리 추가 // 새 엔트리는 테이블의 끝에 위치하게 됨 int new_entry = nof + raw_table->NumberOfDeletedElements(); int new_index = raw_table->EntryToIndexRaw(new_entry); raw_table->set(new_index, *key); // kChainOffset = entrysize : Set(1), Map(2) raw_table->set(new_index + kChainOffset, Smi::FromInt(previous_entry)); // 5. 버킷을 새로운 엔트리로 지정 raw_table->set(HashTableStartIndex() + bucket, Smi::FromInt(new_entry)); // 6. 전체 엘리먼트 수 증가 raw_table->SetNumberOfElements(nof + 1); // 7. 수정된 테이블 반환 return table; } template <class Derived, int entrysize> MaybeHandle<Derived> OrderedHashTable<Derived, entrysize>::EnsureCapacityForAdding( Isolate* isolate, Handle<Derived> table) { // 1. 테이블이 오래된 상태가 아닌지 확인 DCHECK(!table->IsObsolete()); // 2. 테이블의 현재 요소, 삭제된 요소, 용량 정보 가져오기 int nof = table->NumberOfElements(); int nod = table->NumberOfDeletedElements(); int capacity = table->Capacity(); // bucket * 2 // 3. 테이블에 추가 요소를 수용할 만큼의 용량이 있다면 현재 테이블 반환 if ((nof + nod) < capacity) return table; int new_capacity; // 4. 테이블이 비어있는 경우 초기 용량 할당 if (capacity == 0) { // 비어있는 상태에서 초기 최소 용량(4)으로 증가 new_capacity = kInitialCapacity; } else if (nod >= (capacity >> 1)) { // 5. 삭제된 요소가 용량의 절반이상인 경우, 새 테이블을 할당하지 않고 삭제된 엔트리만 제거 // 단, 제거된 엔트리를 그대로 유지할 수 없기 때문에 항상 새로운 테이블을 할당 new_capacity = capacity; } else { // 6. 그 외의 경우, 현재 용량의 두 배로 용량 증가 new_capacity = capacity << 1; } // 7. 새로운 용량으로 리해싱을 수행하고 결과를 반환 return Derived::Rehash(isolate, table, new_capacity); } bool OrderedHashTable<Derived, entrysize>::Delete(Isolate* isolate, Tagged<Derived> table, Tagged<Object> key) { // 가비지 컬렉션 비활성화 블록 DisallowGarbageCollection no_gc; // 1. 테이블에서 키에 해당하는 엔트리 찾기 InternalIndex entry = table->FindEntry(isolate, key); if (entry.is_not_found()) return false; // 2. 테이블의 요소 및 삭제된 요소 수 얻기 int nof = table->NumberOfElements(); int nod = table->NumberOfDeletedElements(); // 3. 엔트리 인덱스를 실제 테이블 인덱스로 변환 int index = table->EntryToIndex(entry); // 4. 엔트리를 비우기 (The Hole로 설정) Tagged<Object> hole = ReadOnlyRoots(isolate).the_hole_value(); // entrysize : Set(1), Map(2) for (int i = 0; i < entrysize; ++i) { table->set(index + i, hole); } // 5. 테이블의 요소 및 삭제된 요소 수 갱신 table->SetNumberOfElements(nof - 1); table->SetNumberOfDeletedElements(nod + 1); // 6. 삭제 성공을 나타내는 true 반환 return true; } // 주어진 해시값에 대한 엔트리의 인덱스를 반환하는 함수 int HashToEntryRaw(int hash) { // 1. 주어진 해시값으로부터 버킷을 계산 int bucket = HashToBucket(hash); // 2. 해시 테이블의 시작 인덱스로 부터 해당 버킷의 엔트리를 가져옴 Tagged<Object> entry = this->get(HashTableStartIndex() + bucket); // 3. 엔트리를 Smi(작은 정수)로 변환 int entry_int = Smi::ToInt(entry); // 4. 디버깅을 위한 확인: 엔트리는 kNotFound이거나 0 이상의 값이어야 함 DCHECK(entry_int == kNotFound || entry_int >= 0); // 5. 엔트리의 정수값 반환 return entry_int; } // 주어진 해시값에 대한 버킷을 반환하는 함수 int HashToBucket(int hash) const { // 버킷의 수는 2의 제곱 수 이기 때문에 -1을 해주면 1111 같은 마스크가 생성 // 결론적으로 나머지 연산과 같음 return hash & (NumberOfBuckets() - 1); //NumberOfBuckets 초기 값은 2 } template <class Derived> Handle<Derived> SmallOrderedHashTable<Derived>::Rehash(Isolate* isolate, Handle<Derived> table, int new_capacity) { // 1. 새로운 용량이 최대 용량을 초과하는지 확인 DCHECK_GE(kMaxCapacity, new_capacity); // 2. 새로운 테이블 할당 Handle<Derived> new_table = SmallOrderedHashTable<Derived>::Allocate( isolate, new_capacity, Heap::InYoungGeneration(*table) ? AllocationType::kYoung : AllocationType::kOld); int new_entry = 0; { // 3. GC 비활성화 블록 DisallowGarbageCollection no_gc; // 4. 기존 테이블의 엔트리를 순회하면서 처리 for (InternalIndex old_entry : table->IterateEntries()) { Tagged<Object> key = table->KeyAt(old_entry); // 5. 빈 엔트리 (The Hole)는 무시하고 계속 진행 if (IsTheHole(key, isolate)) continue; // 6. 키의 해시값 계산 int hash = Smi::ToInt(Object::GetHash(key)); // 7. 새로운 테이블에서의 버킷 및 체인 정보 얻기 int bucket = new_table->HashToBucket(hash); int chain = new_table->GetFirstEntry(bucket); // 8. 새로운 테이블에서의 체인 및 엔트리 정보 설정 new_table->SetFirstEntry(bucket, new_entry); new_table->SetNextEntry(new_entry, chain); // 9. 엔트리의 데이터 복사 for (int i = 0; i < Derived::kEntrySize; ++i) { Tagged<Object> value = table->GetDataEntry(old_entry.as_int(), i); new_table->SetDataEntry(new_entry, i, value); } // 10. 다음 새로운 엔트리 인덱스로 증가 ++new_entry; } // 11. 새로운 테이블의 요소 수 설정 new_table->SetNumberOfElements(table->NumberOfElements()); } // 12. 새로운 테이블 반환 return new_table; }
어떻게 살아야 하나