자바의 자료구조 - Map

 : Map은 Collection 인터페이스와 별개이지만, 
     json형식과 유사한 key-value 자료구조로 자주 사용되는 구현체이다.
     사전과 같은 형태의 자료구조로, ( 사전과 달리 순서는 없다. )
     중복된 key를 가질 수 없고 각 key는 오직 하나의 value에만 mapping될 수 있다.

     Map 인터페이스를 구현한 클래스는 HashMap, TreeMap, LinkedHashMap, Hashtable 이 있다.
     
     Hashtable은 null을 허용하지않고, HashMap은 null을 허용한다. 

     심지어 HashMap은 Key, Value에 모두 null이 허용되고,

     HashTable은 Key, Value에 모두 null이 불가하다.

     ( 타 ide는 모르겠지만, 이클립스의 경우 코딩에 오류는 발생하지 않지만, 실행시 오류가 발생한다. )

     HashMap은 해싱 테이블에 데이터를 저장하고, TreeMap은 탐색 트리에 저장한다.
     ( 키들을 정렬된 순서로 방문할 필요가 없다면, HashMap이 약간 더 빠르다. 당연하지만 )

 

 

 : Hashtable

     Hashtable은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다.

     빠르게 데이터를 검색할 수 있는 이유는 내부적으로 배열( 버킷 )을 이용하여 데이터를 저장하기 때문인데,

     Hashtable은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 활용해

     값을 저장하거나 검색하게 된다.

     실제 값이 저장되는 장소를 버킷 또는 슬롯이라 한다.

     

     저장되는 과정을 좀 더 자세히 살펴보자.

     (Key, Value) 가 ("홍길동", "1234") 인 데이터를 크기가 16인 Hashtable에 저장한다면,

     index = hash_function("홍길동") % 16 의 연산을 통해 index를 연산한다.

     그 이후 hashtable[index] = "1234" 로 데이터를 저장하게 된다.

 

     이렇게 저장되는 Hashtable의 index는 정수이기 때문에 속도가 굉장히 빠르다.

     또한 적절한 hash_function()을 사용하게 된다면, 정확하게 데이터의 유일성을 확인할 수 있으므로

     많은 곳에 사용된다. 

     위에서 언급된 "1234"를 저장하는 곳은 데이터의 크기가 16인 Hashtable에 저장하는 것.

     저장공간이 너무 작다고 생각되진 않는가?

     여기서 Value에 list등을 사용함으로서 좀 더 효율적으로 자료구조를 형성하게 된다.

     hash_function() % 16 등으로 데이터의 index를 구분지어, 16분할을 하게되고, ( 16은 임의의 값 )

     검색하고자하는 데이터의 key값의 index를 구하면 전체데이터를 찾을 필요 없이

     해당하는 index의 저장공간만 탐색하면 되기 때문이다.

 

     그렇기때문에 hash_function()을 형성하는 hash algorithm을 잘 구축하는 것이 중요하다.

     데이터가 index에 적절히 분포되어야 데이터를 탐색할 때 어떤 경우는 10개중에서 찾고,

     어떤 경우는 10000000개 중에서 찾는 불상사를 피할 수 있기 때문이다.

 

     이때 한 index에 여러개의 데이터가 들어가 충돌현상이 발생하는 것을 collision 이라 한다. 

     ( 꼭 이 경우만을 지칭하지는 않고, 충돌을 전부 그렇게 칭한다.

       ex) hashcode가 다른데 같은 index를 배정받는 경우 혹은 Key가 다른데 같은 hashcode를 생성하는 경우가 된다. )

 

     이러한 hashtable의 탐색의 시간복잡도는 O(1) 이다. collision이 발생하는 경우

     최대 시간 복잡도는 O(n)까지 증가할 수 있다.

 

     해시함수에 대해서는 더 깊은 내용이 많지만, 알고리즘을 위한 자료구조의 흐름에 약간 부적합해 

     제외하겠다. 

    https://mangkyu.tistory.com/102 여기에 잘 나와있으니 필요시 참고하도록 하자.

 

     Hashtable은 Thread-safe하다. ( HashMap은 Thread-safe하지 않다. )

     멀티스레드 환경이 아니라면 Hashtable은 HashMap보다 성능이 떨어진다.

     자세한건 아직 모르지만, Thread-safe를 위한 자원이 필요한 것이 아닐까 싶다.

     이 부분은 HashMap을 아래에서 살펴보면서 다뤄보자.

     또한, HashMap에서는 차이점을 위주로 알아보자.

 

 

 

 : HashMap

     HashMap은 Hashtable과 상당히 유사하다. 고로 차이점을 위주로 짚어보자.

     Enumeration여부 : Hashtable은 not-fail-Enumeration, HashMap은 Enumeration 제공하지 않음

     HashMap은 보조해시를 사용, Hashtable은 보조해시를 사용하지 않음.

     HashMap이 collision이 덜 발생할 수 있어 성능상 이점 있음.

     Hashtable의 구현에는 변화가 거의 없지만, 지속적으로 HashMap은 개선되고 있음

     여기까지 봐도 Hashtable의 사용성에 대해 의문이 들테지만, 좀 더 자세히 언급하면

     Hashtable은 컬렉션 프레임워크가 만들어지기 전에 사용되던 것으로, 기존의 클래스들과의 호환을 위해

     남겨두었기 때문에 사용하지 않는 편이 좋다.

 

 

 

 

 

 메소드

     .put(key,value) : key값에 value를 매핑시켜 HashMap에 저장한다.

     .remove(key) : 해당 key값에 대한 데이터를 삭제한다.

     .entrySet() : Map을 Set으로 변환한다. 

 

     이렇게 확인해 볼 수 있는데, Map도 Map이지만 entrySet은 Set인데 어떻게 순서를 나타낼 수 있는지 궁금했다.

 

 

     보면 Set<Map.Entry<K,V>> 의 타입으로 보여진다.

     Map의 형태를 원소로 갖는 Set이기에 순서를 유지할 수 있는지 궁금했다.

     좀 알아본 바로는, Hashtable에서 배웠듯, key값으로 index를 만드는데 원소가 적고,

     단순한 Integer형태이기 때문에 index역시 순서대로 배정을 받게되고

     그렇기 때문에 Map은 순서를 갖게된다.

     그러한 Map을 순차적으로 Set으로 옮겼기에 순서를 갖는 것처럼 보여지는 것이라고 생각된다.

 

     그래서 실험을 해보았다. HashMap을 구성하는 Node Array ( 버킷 )의 기본 사이즈는 16이다. 

     ( 기본 생성자의 경우 )

     그렇다면 index는 Hashtable에서 보았듯, hash_function() % 16의 형태로 index를 구축하게 되고

     그 이상의 Key값을 만들경우 순서가 유지되지 않는 것을 확인 할 수 있을 것이다.

     

     라고 생각했다.  나는 17부터는 1과 같은 index기에 1과 17이 순서에 상관없이 같이 묶음으로 나오지 않을까

     기대했는데 뭔가 착오가 있던 모양이다. 고로 이 부분은 추후 포스팅하겠다.

 

 

 : TreeMap

     TreeMap은 대다수의 경우 성능이 HashMap보다 떨어진다.

     TreeMap은 데이터를 저장할 때 즉시 정렬하기에 추가나 삭제가 오래 걸린다.

     하지만 정렬된 상태로 Map을 유지해야 하거나 정렬된 데이터를 조회해야 하는

     범위 검색이 필요한 경우 TreeMap을 사용하는 것이 효율성면에서 좋다.

 

     TreeSet과 동일하게 레드 블랙 트리를 이용해 정렬한다. 

 

 

 : LinkedHashMap

     이미 LinkedHashSet, HashMap에 대해 알고 있을테니 추가적으로 기술할 필요가 없어보인다.