방앗간

※ 양수 변환 - 보수의 성질을 활용해 값을 양수로 변환하는 방법 다음 예시와 같이 연산하는 경우 해시(테이블)에 포함되는 양수로 표현할 수 있다. Java 에선 음수를 표현하기 위해 2의 보수를 활용하는데 첫 숫자가 0인 경우는 양수고 1인 경우는 음수이다. 해당 방법을 활용해 data를 배열의 어느 위치에 넣을지를 결정할 수 있다. //data의 index 결정 int hashval = data.hashCode(s); hashval = hashval & ox7FFFFFFF; hashval = hashval % tableSize;

※ 해시 크기 최적화(Compressing Hashcode) - 해시 충돌을 방지하고자 해시 크기를 최적화 할 필요가 있다. 예1: 해시 크기를 홀수로 설정해 % 연산자 사용시 다양한 결과가 나오게 한다. 예2: 해시 크기 소수 설정해 나머지가 다양한 숫자가 나오게 한다.

※ 해시 함수 문자열 - 문자열 this 를 해시로 나타내려면 어떻게 해야할까? 문자는 유니코드 변환을 통해 숫자 형태로 표현할 수 있는데 이를 이용하여 각 문자를 변환하고 숫자를 합하면 문자열을 숫자로 표현할 수 있을 것 이다. 하지만 이렇게 변환하는 경우, this뿐 아니라 hits, tish등 다른 문자열도 동일한 숫자로 표현이 되는 해시 충돌이 발생하게 되는데, 여기에 어떠한 상수 g를 문자의 위치만큼 제곱하고 그 수를 곱할경우 문제가 해결이 된다. 문자열을 해시로 표현하는 함수는 다음과 같이 표현할 수 있다. public int hashCode(String s){ int g = 31; int hash = 0; //문자열 숫자로 표현 //상수 g 문자 위치만큼 제곱 후 곱하기 for(int i=0..

※ 해시충돌 - 해시 충돌이란 해시 함수가 서로 다른 두 개의 입력값에 대해 동일한 출력결과를 나타내는 상황을 의미하는데, 해시 함수가 무한한 가짓수의 입력값을 받아 유한한 가짓수의 출력값을 생성하는 경우, 비둘기집 원리에 의해 해시 충돌은 항상 존재할 수 밖에 없다. 암호학적 해시 함수의 경우에는 해시 함수의 안정성을 깨뜨리는 충돌 공격의 가능성을 고려하여야 하기 때문에 의도적인 해시 충돌을 만드는것이 어렵도록 해야한다. 앞서 설명했듯이 서로 다른 값을 가진 키가 일치하는 경우를 해시 충돌이라고 하는데 다음 예시와 같이 전화번호를 3분할한 것들의 합을 키로 지정하였는데 동일하게 2386이라는 값이 나오는 경우 해시 충돌이 발생했다고 볼 수 있다. 출처: 자바로 구현하고 배우는 자료구조

※ 해시함수 ○ 특징 - 데이터의 속성을 고려해야 한다 - 계산 시간이 빨라야 한다 - 두 요소가 동일한 경우 "동일한" 값을 반환해주어야 한다 - 같은 실행환경인 경우 같은 객체라면 같은 값이 나와야 한다 - 코드를 새로 실행하면 객체가 동일하더라도 다른 값이 나올 수 있다 - 가능한 코드에서 충돌이 발생하지 않도록 해야한다.

※ 해시(Hash) - 연결 리스트의 단점은 리스트에서 찾고자 하는 요소의 탐색 방법이 무조건 모든 요소를 다 둘러봐야 한다는 점인데 이 단점을 보완하는 것이 바로 해시인데 해시는 데이터를 빠르게 추가하거나 제거하도록 하는 데이터 구조이다. 해시는 키 그리고 키와 연관된 값을 가지고 있다. 모든 요소를 확인한 뒤 동일한 노드를 찾는 연결 리스트와 달리, 해시에서는 키가 주어지면 바로 연관된 값을 찾을 수 있다.

배열에는 순서가 있어서 첫 부분을 제거하거나 추가하고자 한다면, 요소들을 하나씩 뒤로 옮겨야 하고 이 시간 복잡도는 O(n)이 된다. 이는 스택과 큐 과정에서 비효율적이라 판단을 하기 때문에 스택과 큐에서는 기본적인 배열을 사용하지 않는다. 연결 리스트는 배열 맨 앞을 가리키는 head 포인터를 사용하는데 이로인해 리스트의 첫 부분을 제거하거나 추가하는 과정의 시간 복잡도가 상수이고 보다 효율적인 알고리즘인 연결 리스트는 스택과 큐를 하는데 사용이 된다. 일반적으로 배열은 연결 리스트보다 빠르고 메모리도 덜 차지하지만 크기가 정해져 있다는 특징이 있다.

※ 원형 연결 리스트 - 원형 연결 리스트는 마지막 next 포인터가 연결 리스트의 노드를 가리키는 연결 리스트이다. 원형 연결 리스트의 마지막 next 포인터가 head를 가리키는지 확인하는 방법은 다음과 같다. head 에서 시작하여 t == null 이 될 때까지 반복한다면, 시간복잡도는 O(n) 이다. tail 포인터를 사용하는 경우, 시간복잡도는 O(1) 이다. 그리고 next 포인터가 임의의 노드를 가리키는 경우 확인하는 방법은 다음과 같다. tail에서 시작해 tail 포인터가 다시 나타나는지 확인한다. 시간복잡도는 O(n)이다. 임시 포인터 2개를 사용해 시작점을 잡고 currentSize 만큼 떨어진 노드를 확인하고 시작점을 다음으로 옮겨 동일한 노드가 나올때까지 반복하는데 이 시간복잡도..

※ 이중 연결 리스트 - 이중 연결 리스트는 단일 연결 리스트에 바로 직전의 노드를 가리키는 previous 포인터를 추가한 연결 리스트이다. removeLast 메소드를 사용할 때, 단일 연결 리스트는 tail 포인터가 있어도 O(n)의 시간 복잡도로 모든 노드를 한 번은 거쳐야 한다는 단점이 있었지만 이중 연결 리스트는 tail 포인터가 가리키는 노드에서 previous 포인터가 가리키는 노드를 찾으면 되어서 시간 복잡도가 O(1)이 된다. 이중 연결 리스트의 단점은 previous 포인터가 추가되기 때문에 노드를 추가하는 과정이 더 복잡해진다는 점이다.

※ 반복자 - 배열의 각각의 원소를 출력할 때, 다음과 같이 코드를 작성할 수 있다 int arr[] = {1, 2, 3, 4, 5}; for (int i=0; i