[Java] Collection

Set

• 순서를 유지하지 않고 저장
• 중복 저장 불가

모든 원소가 1개씩만 존재할 수 있음 !!

HashSet

hash function : 임의의 크기를 가진 데이터를 고정된 크기의 데이터로 매핑하는 함수

예) Mod 8 >> 0, 1, 2, 3, 4, 5, 6, 7

HashSet에서는 Hash Function으로 구한 인덱스에 따라 데이터를 저장한다.

우리가 저장하고 싶은 값을 8로 나눈 나머지 > Index 가 된다고 생각할 수 있다.

해시함수 한번만 실행하면 바로 데이터가 저장된 위치를 알 수 있기 때문에,
검색과 저장이 매우 빠르다.

Hash 충돌

아쉽게도 해시 함수는 완벽하진 않다. 다른 Key임에도 동일한 Hash값을 갖는 경우가 있는데, 이것을 Hash 충돌이라고 한다.
그 원인은 여러가지가 있겠지만,

1. 진짜 둘이 같은 Key임
2. 해시 함수로 변환 결과 같은 값. 예) 8과 16 >> 매핑 결과 둘다 0

Linked List를 활용해 데이터를 저장하면 해결이 가능.

public class _HashSet_p2 <E>{

    private static final int DEFAULT_CAPACITY = 10;
    private int arraySize = 10;
    protected Object[] elementData;
    private int size;

    public _HashSet_p2() {
        elementData = new Object[DEFAULT_CAPACITY];
    }

    public int size(){
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    protected int hash(E e){
        // hashCode : -21억 ~ +21억
        // 0 ~ 21억 사이의 값 반환
        int hashCode = Math.abs(e.hashCode());
        return hashCode % arraySize;
    }

    private void resize(){
        arraySize *= 2;
        Object[] temp = new Object[arraySize];

        for (int i = 0; i < elementData.length; i++) {
            if (elementData[i] == null) continue;
            int newIndex = hash((E) elementData[i]); // 강제 casting
            temp[newIndex] = elementData[i];
        }

        elementData = temp;
    }

    public boolean add(E e){
        Node<E> node = new Node<E>(e); // node는 참조 타입임.

        if (size == arraySize-1){
            resize();
        }

        int index = hash(e);
        Node<E> head = (Node<E>) elementData[index]; // 첫 번째 노드는 elementData의 index에 위치하는 노드

        if (head == null){              // input 값이 Set에 없는 경우
            elementData[index] = node;
            size++;
            return true;
        }

        Node<E> link = head; // link 노드에 head 할당
        while (link.next() != null){ // link 의 다음 노드가 없을때까지 반복
            if (link.equals(node)) return false; // 중복값이 존재하면 false 반환
            link = link.next();
        }

        link.setNext(node); // input 값이 들어있는 노드를 link의 다음 노드로 지정
        size++;
        return true;
    }

    public boolean remove(E e){
        int index = hash(e);
        Node<E> head = (Node<E>) elementData[index];

        if (head.data().equals(e)){
            elementData[index] = head.next(); // 참조를 다음 노드로 옮겼으므로 이전의 노드는 GC에 의해 삭제됨
            size--;
            return true;
        }

        Node<E> prevNode = head;
        Node<E> link = head;

        while (link.next() != null){
            prevNode = link;        // 하나씩 다음 노드로 옮김
            link = link.next();

            if (link.data().equals(e)){ // 새로운 연결 노드의 값이 지우려는 값과 같으면
                prevNode.setNext(link.next()); // 이전 노드의 참조를 다음 노드로 변경함
                size--;
                return true;
            }
        }
        return false;
    }

    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        sb.append("[");

        for (int i = 0; i < elementData.length; i++) {
            if (elementData[i] == null) continue;
            Node<E> link = (Node<E>) elementData[i];

            while (link.next() != null){
                sb.append(link.data()).append(","); // 메서드 체인방식
                link = link.next();
            }

            sb.append(link.data());
            if (i != elementData.length-1) sb.append(",");
        }

        sb.append("]");
        return sb.toString();


    }
}

Map

• Key와 Value의 쌍(Entry)으로 저장
• Key는 중복 저장 불가, Value는 가능
• Key로 Value를 추출할 수 있다는 점이 특징

HashMap

자바의 HashMap 클래스에는 매개변수로 Key와 Value를 갖는다.

public class _HashMap <K, V> {

    private final _EntrySet<_Entry<K,V>> entrySet = new _EntrySet<>();

    public V put(K key, V value){
        _Entry<K, V> entry = new _Entry<>(key, value);
        if (entrySet.add(entry)){
            return value;               // 추가한 entry의 value return
        }

        return null;
    }

    public V get(K key){
        _Entry<K, V> entry = entrySet.get(new _Entry<>(key, null));
        if (entry == null) return null; // 존재하지 않는 Entry 라면 null
        return entry.getValue(); // 존재하면 Value return
    }

    public V remove(K key){
        _Entry<K, V> entry = entrySet.get(new _Entry<>(key, null));
        if (entry == null) return null;

        V value = entry.getValue();
        entrySet.remove(entry);
        return value; // 엔트리 삭제와 동시에 value 출력
    }

    public _HashSet_p2<_Entry<K,V>> entrySet(){
        return entrySet;
    }

    public boolean containsKey(K key){
        return get(key) != null;
    }

    @Override
    public String toString() {
        return entrySet.toString();
    }
}

Stack

한 쪽 끝에서만 자료를 넣고 뺄 수 있는 선입후출 형식의 자료구조
예) Ctrl + Z를 누르면 가장 최근 수정내역으로 되돌림

peek : 맨 위의 원소를 찾음 > 삭제되지 않고 출력
pop : 맨 위의 원소를 꺼냄 > 원소가 삭제되면서 출력
push : 새로운 원소를 맨 위에 넣음

public class _Stack<E> implements Iterable<E> {

    private Node<E> top;
    private int size;

    public int size(){
        return size;
    }

    public void push(E e){
        Node<E> node = new Node<>(e); // Node 로 wrapping 하기
        if (top != null){
            node.setNext(top);
        }

        top = node;
        size++; // setNext
    }

    public E pop(){
        if (top == null) return null;
        E data = top.data();
        top = top.next();
        size--;
        return data;
    }

    public E peek(){
        if (top == null) return null;
        return top.data();
    }

    public boolean empty(){
        return size == 0;
    }

    // LIFO 를 지켜서 요소를 반환하는 Iterator


    @Override
    public Iterator<E> iterator() {
        return null;
    }
}

Queue

먼저 넣은 데이터가 먼저 나오는 선입선출 형식의 자료구조
예) 은행 대기열
peek : 맨 앞의 원소를 출력
poll : 맨 앞의 원소를 꺼냄
offer : 새로운 원소를 맨 뒤에 넣음

public class _Queue<E> {

    private Node<E> top;
    private Node<E> tail; // 마지막을 기억하면 연산 속도가 빨라짐
    private int size;

    public void offer(E e){
        Node<E> node = new Node<>(e);

        if (top == null){
            top = node;
            tail = node;
            size++;
            return;
        }
        tail.setNext(node);
        tail = node;
        size++;
    }

    public E peek(){
        if (top == null) return null;
        return top.data();
    }

    public E poll(){
        if (top == null) return null;
        E data = top.data();
        top = top.next();
        size--;
        return data;
    }

    public boolean empty(){
        return size == 0;
    }

    public int size(){
        return size;
    }
}