Java - Collection Basic & Hash Basic

  • Deep 한 내용이 아닌, 가벼운 Basic 한 내용만 담았다.

1. List

  • 동일한 객체 타입에 대하여 중복을 허용하며, 입력한 순서를 유지하고, 빈틈 없이 데이터를 적재하는 자료구조이다.

  • 기본 크기는 10이며, 부하율이 0.75가 넘어가면 크기를 확장한다.

    • 확장은 내부적으로 알아서 이루어지며 크기를 추가로 늘린 새로운 리스트를 생성하고 거기에 옮겨 담는다.

    • 초기 크기를 직접 지정할 수 있기 때문에 리스트의 크기가 확정적으로 클 것이라면, 초기 크기를 크게 잡아두는 것도 좋다.

        List<String> testList = new ArrayList<>(100); // 초기 크기 100

  • ArrayList, LinkedList 등이 있다.



2. Set

  • 중복을 허용하지 않는 특징이 있다.

  • HashSet
    • 가장 일반적임
  • TreeSet
    • 정렬된 순서를 보장한다. 그러나 입력한 순서를 보장하지는 않는다.
  • LinkedHashSet
    • 입력한 순서를 보장한다.



3. Queue

  • 선입선출(FIFO) 방식을 사용하며 선언 시에 LinkedList<>로 구현체를 만드는 것이 일반적이다.

  • 그러나 우선순위에 따라 요소를 관리하는 PriorityQueue<>나, 큐의 두 끝에서 요소를 추가하거나 제거할 수 있는 ArrayDeque<>로 상황따라 선언하기도 한다.

  • offer() 와 poll() 그리고 peak() 등의 메서드가 있다.



4. Stack

  • 후입선출(LIFO) 방식을 사용한다.

  • JVM 메모리 스택 영역과 동일한 방식의 자료구조이다.

  • push(), pop(), peak() 등의 메서드를 사용한다.



5. Hash

5.1. Hash Basic

  • 일반적으로 데이터를 고정된 크기의 값으로 변환하는 알고리즘 또는 함수를 의미한다.

  • key와 Value로 나뉘어져 있으며, Key를 가지고 Value를 찾는 방식이다.

  • Map에서 하나의 Key, Value가 저장되어있는 공간을 버킷이라고 한다.

  • HashTable, HashMap, ConcurrentHashMap 등이 있다.

    • HashTable은 Null을 허용하지 않고, 현재는 별로 사용하지 않는다. 동기화는 지원하지만 성능이 좋지 않다.

    • HashMap은 Null을 허용하고, 일반적으로 많이 쓰인다. 그러나 동기화를 지원하지 않아 멀티 스레드 환경에서는 적합하지 않다.

    • ConcurrentHashMap은 Null도 지원하고 동기화도 지원한다. 내부에서 데이터를 관리하는데 해시 버킷을 분할하여 여러 섹션으로 나누어 동시성을 향상시킨다.


5.2. Hash Collision ( 해시 충돌 )

  • Hash는 Key값을 hashcode로 먼저 비교를 한 후 equals로 비교를 한다.

  • 이 때 둘 다 같으면, 아예 동일한 Key로 간주하고 값을 덮어씌운다거나 한다.

  • 그러나 hashcode는 같고, equals 만 다른 경우가 있다.

  • hashcode 는 기본적으로 오버라이딩 되어있지 않다면, 기본으로 제공하는 해시 함수의 결과로 hashcode 를 만든다.

  • HashMap 은 그 hashcode 값의 버킷에 value 를 저장한다.

  • 예를들어, value % 3 == index 이라는 해시 함수를 재정의 하였다.

  • 그러면, value 가 3 인 녀석과, 6인 녀석은 모두 0 이라는 index를 갖게되고,

  • index 0 에 3과 6이 들어가고자 충돌하게 된다.

  • 이 때 자바에서는 노드 갯수가 8개가 되기 전까지는 LinkedList 로 관리해준다.

    • 즉, index 0 에는 3이 있고, 그 뒤에는 6이 있다 이런 식으로 관리를 해주는 것이다.

    • 그러다가 노드 갯수가 8개가 되면 Red-Black Tree 구조로 저장하게 된다.

    • 그러다가 다시 노드가 삭제되어 갯수가 6개가 되면 LinkedList 로 돌아온다.

      • 둘 다 기준점이 8개면, 그 경계선에서 불필요한 자료구조가 겹치게 일어날 수 있기 때문이다.


  • 이걸 실험하기 위해 Integer a = new Integer(7); Integer b = new Integer(7); 을 Hash에 넣어 실험하려 하였으나 실패하였다.

    • Integer는 hashcode가 곧 value 값이 되게끔 재정의 되어있기 때문이다.

    • 그리고 신기한 점을 발견하였는데, Integer는 -128 ~ 127까지는 같은 객체 주소를 공유한다.

    • 즉, Integer a = new Integer(1); 과 Integer b = new Integer(1); 을 하면

    • a == b가 true가 나온다.

    • 근데 Integer a = new Integer(130);Integer b = new Integer(130); 일 때

    • a == b를 하면 false가 나온다.


  • 이 방법 외에도 LoadFactor 로 관리하는 원초적인 방법 또한 있다.


5.3. Load Factor

  • Set과 Map 에서는 로드 팩터를 기반으로 해당 객체의 저장 공간을 조절한다.

  • Set과 Map 에서는 로드 팩터를 기반으로 해당 객체의 저장 공간을 조절한다. 로드 팩터는 기본적으로 (데이터의 개수)/ (저장 공간) 을 의미하며, 이를 기반으로 Map과 Set의 크기를 리사이즈 한다.

  • 기본적으로 부여되는 Map 공간 크기는 16이다.

  • 초기에 생성자를 통해 초기 공간 크기와 로드 팩터를 정해줄 수 있다.

  • 들어오는 데이터에 비해 로드 팩터가 작을 경우 해시 충돌 및 링크드 리스트를 통한 Separate Chaining이 많이 발생한다. 반대로, 들어오는 데이터에 비해 로드 팩터가 클 경우 메모리 낭비가 발생한다. 따라서 이를 고려하여 설정해야 한다. 일반적으로 0.75의 로드 팩터를 설정하는 것을 이상적으로 생각한다.


  • 로드 팩터가 0.75로 기본 설정이 되어있는데, 이렇게되면 100개의 버킷중 75개의 버킷이 차게되면

  • 버킷의 갯수를 늘려준다.

  • 이 때 해시함수 계산을 통해 index 를 재배치 해주며, 원래 있던 값도 복사해서 새로운 해시로 넘겨줘야 한다.

  • 그래서 이 작업이 빈번하게 일어나게 될 경우 성능이 떨어질 수 있다.

  • 이 방법은, 버킷 수를 늘려서 해시 충돌 가능성을 낮추는 자바의 원초적인 방법이다.


5.4. 좋은 Hash 함수

  • 우리가 hashCode 를 만드는 함수를 재정의 할 때,

    • 계산 속도가 빠른 것

    • 결과 값이 균등 하게 분포 되는 것

    • 어떤 입력 값도 지정된 길이의 츨력 값으로 바꿀 수 있을 것

    • 일방향성을 띌 것

  • 이 부분을 고려하여 만들어야 한다.

  • 이미 존재하는 해시함수 알고리즘이 여러개가 있다. 거기서 선택하는 것이 가장 좋다.






results matching ""

    No results matching ""