💡 hashCode 객체의 주소값을 변환하여 생성된 객체의 고유한 정수값이다. 두 객체가 동일한 객체인지 동일성을 체크할 때 사용한다. 특징 해시 함수에 중요한것은 데이터의 속성이다. 연산이 빨라야 한다. 최대한 코드 충돌을 지양해야한다. 코드를 재실행 했을떄 같은 객체라도 다른 값이 나올 수 있다. Object의 hashCode()를 Override 해야한다. Object 클래스의 hashCode는 메모리 위치를 기반으로 실행된다. 재실행마다 객체는 다른 위치에 저장되기 때문에 다른값이 반환된다. 같은 실행 환경일 경우 두 요소가 같다면 항상 같은 값을 반환해야 한다. (equals) 객체의 경우 힙에서의 위치, 문자열의 경우는 문자열 비교 등 예시 아래 예시의 person1과 person2의 hash..

💡 Hash Chaining 가장 안정적이며 보편적으로 사용되는 자료구조 중 하나이다. 파이썬의 딕셔너리도 이것을 기반으로 만들어졌으며 자바에서도 쉽게 해시를 만들 수 있게 API를 제공한다. 펄에서도 이 방법으로 연상 배열과 해시를 만든다. 해시는 사실상 배열 1개로 구성되어 있으며, 요소들이 들어가야 할 위치에 추가되면서 배열은 점점 채워진다. 그래서 배열의 위치마다 새로운 자료구조를 만들면서 수많은 데이터를 수용할 수 있도록 만드는것이다. 즉, Hash 배열의 각 요소에 자료구조인 LinkedList를 사용하며 각 요소는 테이블의 크기보다 클 수 있다. 어떤 자료구조가 가장 적합할까? 정답은 LinkedList 이다. 체인을 만들기 위해 배열의 각 위치마다 LinkedList를 만들어 주는 방법이며..

💡 선형조사법 (Linear Probing) 채우려는 공간이 이미 차 있다면, 비어있는 칸을 찾을 때까지 다음 칸을 확인하는 방법이다. 비어있는 칸을 찾아 그 곳에 채운 후 위치가 바뀌었다는 사실을 알려야 한다. 예시 객체 x 객체 x의 hashCode 값인 h를 구한다. h를 양수로 변환 -> h & 0x7FFFFFFF; 테이블의 크기와 % 연산 -> h % table.size(); h를 가지고 x를 적절한 위치로 저장, 이 때 위치는 hashCode의 값에 따라 다름 객체 y 위와 동일한 방법으로 h를 구한다. x의 위치와 동일한 값이 나오면 x의 위치에 y를 저장해야 한다. 이런 상황을 충돌이라고 한다. 해결 x의 다음 칸에 y를 저장 y의 위치가 바뀌었다는 사실을 알려야 한다.\ 삭제의 경우 데이..

💡 해시 충돌 서로 다른 값의 키가 일치하는 경우를 의미한다 충돌이 일어나지 않게 Folding 하는 방법 함수를 구현할때 충돌을 피하고자 할때 어떻게 분포를 더 넓게 할지 생각하기 아래 사진은 전화번호를 받아서 3분할한 합을 키 배열에 저장하는 도중 Folding이 발생한 사진이다 hashCode에서의 충돌문제를 해결한 문자열 표현 문자는 유니코드로 변환하여 숫자로 나타낼 수 있고, 각 문자를 변환 후 그 숫자들을 합하면 된다 하지만 그렇게 했을 경우 단순히 문자의 위치와 관계없이 같은 문자열이 있다면 해시 충돌이 발생한다 문자의 위치에 따라 상수 g를 곱하는 횟수를 다르게 해서 충돌 문제 해결 116 + g(104 + g(105 + g(115))) // 문자열을 기반으로 정수를 계산해주는 hashCo..

💡 Hash 연결 리스트에 비해 검색 & 추가 & 제거 & 수정의 시간복잡도 효율이 좋은 자료구조인 키 & 값 기반의 Hash Hash -> Key & Value Array의 구조로 가정함 Hash의 메서드 시간복잡도를 효율적으로 바꿀 수 있는 메서드들 add() remove(0 lookup() / find() change() 시간복잡도가 최소 O(n)이 걸릴수 밖에 없는 메서드들 all entries all keys all values Hash에선 시간복잡도가 O(1)이지만 연결 리스트에선 O(n)이던 메서드들 size() isEmpty() isFull() loadFactor() Hash 함수 - hashCode() 해시 함수에 중요한것은 데이터의 속성이다 연산이 빨라야 한다 최대한 코드 충돌을 지양해..

💡 스택 & 큐 스택 & 큐 를 배열로 구현했을 때 배열은 순서가 있고 첫 부분을 제거하거나 추가하려면 요소들을 하나씩 뒤로 옮겨야 하며 시간복잡도는 O(n) 임 스택과 큐의 과정이 비효율적이기 때문에 스택과 큐에서는 기본적인 배열을 사용하지 않음 그래서 첫 부분을 제거하거나 추가하는 과정의 시간복잡도가 상수인 연결 리스트를 스택 & 큐에 적용하는게 좋음 배열로 스택 구현 addLast, removeLast -> O(1)의 시간복잡도 addFirst, removeFirst -> 배열의 원소들은 메모리 상에서 순차적으로 저장되기 때문에 맨 앞에서 삽입/삭제 연산이 일어나면 뒤로 한칸씩 미루거나 앞으로 한칸씩 당겨야 하므로 O(n)의 시간복잡도 Last In First Out (LIFO, 후입선출, 나중에 ..

💡 이중 연결 리스트 & 원형 연결 리스트 이중 연결 리스트(Doubly Linked List) Singly Linked List 관련 포스팅 - https://root-ca.tistory.com/253 전에 만들었던 단순 연결 리스트에 previous 필드를 추가한다 즉, 이중 연결 리스트의 Node 구성은 next & prev & data 3개의 요소가 들어감 원형 연결 리스트(Circular Linked List) tail.next가 null이 아닌 연결 리스트의 노드를 가리키는 연결리스트 단순 연결 리스트의 단점 tail 포인터가 있더라도 removeLast()를 하기 위한 시간복잡도는 O(n)으로 마지막 요소부터 앞으로 넘어갈 방법이 없으므로 비효율적이다. 무조건 처음부터 시작해서 마지막의 2번..