706.Design HashMap (Leet Code)

<내가 짠 코드>

var MyHashMap = function() {
    this.map = {};
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
MyHashMap.prototype.put = function(key, value) {
    this.map[key] = value
};

/** 
 * @param {number} key
 * @return {number}
 */
MyHashMap.prototype.get = function(key) {
    return this.map[key]!==undefined?this.map[key]:-1;
};

/** 
 * @param {number} key
 * @return {void}
 */
MyHashMap.prototype.remove = function(key) {
    delete this.map[key];
};

/** 
 * Your MyHashMap object will be instantiated and called as such:
 * var obj = new MyHashMap()
 * obj.put(key,value)
 * var param_2 = obj.get(key)
 * obj.remove(key)
 */

이렇게 코드를 짰는데, 찾아본 많은 사람들이 this.map = new Array()나 this.map = []와 같이 배열로 짰다. 

나는 HashMap이 뭔지 잘 몰라서 그런거 같아서, 찾아봄. 

"HashMap은 Map의 구현체 중 하나로 자료구조로 배열(array)를 사용한다. 배열은 '인덱스'를 통해 바로 접근이 가능하다는 장점이 있다. HashMap은 해싱(Hashing)을 통해 Map 데이터가 저장 될 위치의 인덱스를 구한다. 그래서 이름이 HashMap이다."

Key값의 인덱스를 통해 Value에 접근하는 형태는 개인적으로는 Map이 더 적당하지 않을까 라고 생각하는 바인데, 아마도 Hashmap이 Array를 자료구조로 사용한다고 하니 Array로 짜여진게 아닌가 싶은 생각이 든다.
(혹시나 제 생각이 틀렸거나 다른 생각이 있으시다면 댓글 달아주시면 너무 감사하겠습니다.)

아래는 위의 글 들을 찾아보다가 궁금해져서 따로 더 찾아본 정보들을 정리해 보았다. 

 

<그렇다면 HashMap을 자바스크립트의 Object로 대체 될 수는 없는가?>

Object는 hashmap 과 같은 기능을 하지만 hashmap은 더 나은 benefit을 제공한다고 한다. 예를 들어, Hashmap은 훨씬 더 높은 flexibility가 있다. hashmap의 key는 array, object등 어떠한 데이터 타입도 가능한 반면, 자바스크립트의 Object는 key로서 integer, strings, symbols 만을 사용할 수 있다.
Hashmap은 linked lists로 구성되어 있어, element들의 순서가 유지되어 순회(반복?)할 수 있다. 또한, Object에 저장 된 key/value 쌍과 다르게 hashmap의 item 수는 size property로 확인할 수 있다. 

*여기서는 Hashmap이 Linked List로 구성 되어있다는 글을 발견해서, 찾아보니 Hashmap은 Linked List와 Array 를 섞어서 사용하고 있다고 한다. (https://medium.com/zero-equals-false/how-hashmap-works-a-missing-piece-of-hood-29dd28c4c01e)
key값의 hash를 저장하는데는 array가 사용되고, data와 key등이 저장되는 곳은 linked List가 사용된다. 

 

<LinkedList와 Array의 차이>

- LinkedList는 내부적으로 node를 가지고 있는 형태이다. node는 값과 다음 node로, 최소 두가지 정보를 가지고 있어야 해서 더 많은 공간을 사용하지만 element를 삽입하고 제거하는 것에 특정 값만 바꿔주면 되기 때문에 시간복잡도는 O(1)이다. 반면 데이터 조회의 경우, 논리적인 주소를 따라가는 순차 접근만 가능하기 때문에 O(n)을 가진다. 
- Array는 연속적으로 공간을 적게 차지하고 element의 index값을 알고 있으면 O(1)으로 해당 원소로 접근 할 수 있지만, 선택한 요소를 삽입하거나 제거하는 과정에서 배열의 연속적인 특징이 깨지게 되어 시간 복잡도는은 O(N)을 가진다.

 

<자바스크립트에서는 Array가 진짜 Array가 아닌 Object이다. >

var arr = new Array(100000);

위와 같은 선언에도 메모리가 할당 되지 않는다. 단지, Array의 속성중 하나 인 length의 value가 새로 설정될 뿐이다.
실제로 값을 가지고 있는 element가 있을때만 배열로서 존재한다. (배열은 Hashtable Object type)

var array = [];
array[0] = "foo"          // Is a resizable array
array[1] = "bar"          // Is a resizable array
array[2] = "baz"          // Is a resizable array
array[1000000] = "hello"; // Is now a hash table
console.log(array[1000000]) // "hello"

위와 같이 array의 중간이 비었을 때, Javascript Engine은 중간의 배열에 값을 할당 하는 것이 아니라, Dictionaly / hashtable과 같은 data structure를 사용하여 메모리 사용을 최소화한다. 따라서 이렇게 중간의 배열이 빌 경우에는, Array에 접근하는 속도가 느려짐.
위와 같이 중간에 배열이 비는것은 피하는 것이 좋음. 

 

<자바스크립트의 Map과 Object의 차이>

1. More Key Types
Object는 Key로서 symbol과 string만 될 수 있다. Map은 어떤 값들도 Key가 될 수 있다.(objects, functions, or primitives)
2. Better Size Determination
Map은 사이즈 속성을 가지고 Object는 size를 알기 힘들다. size를 알기 위한 시간 복잡도가 Map은 O(1)이고 Object는 O(n)이다.
3. Better performance
Maps는 빈번한 entries의 추가와 삭제에 최적화 되어있음.
4. Direct Iteration
Object와 달리 Map은 순회가능함. 
5. Key Order
ECMAScript 2015 이전에, Object의 순서는 보장되지 않았다. Map은 Key의 추가된 순서가 보장됨.
6. No Key Overriding
Object는 prototype으로 인해 기본 Key가 이미 존재한다. 따라서 내가 설정한 Key에 따라 충돌이 일어날 수 있음. Map은 기본 설정되는 Key가 없음. (ECMAScript 2015부터 Object.create(null)을 이용하여 Key Overriding을 방지할 수 있음.)

 

reference
https://blog.naver.com/1012rnjsdydgns/222864391073
https://stackoverflow.com/questions/43855875/how-are-the-javascript-arrays-internally-resizing
https://stackoverflow.com/questions/20321047/how-are-javascript-arrays-represented-in-physical-memory/20323491#20323491
https://medium.com/p/9a272e85f6a8
https://www.reddit.com/r/programming/comments/xtjik9/is_object_a_hashmap_in_javascript/
https://lordofkangs.tistory.com/78
https://medium.com/@martin.crabtree/javascript-tracking-key-value-pairs-using-hashmaps-7de6df598257
https://siahn95.tistory.com/93