-
해시 딕셔너리를
자주 이용하게 되는 경우 중 하나는
-
키를 가지고 어떤 값을
찾고자 하는 경우입니다
-
이런 함수가 있다고 해 봅시다
-
우리가 찾고자 하는 일반적인 값인
V를 반환해주죠
-
그리고 이 값에 해당하는 키를
입력값으로 넣어줄 겁니다
-
어떻게 키를 넣으면
이 값을 반환받을 수 있을까요?
-
방법은 바로 이렇습니다
-
키를 받아서
그 키의 해시 코드를
-
그 다음에는 뭘 하면 좋을까요?
-
양수로 만들어줍니다
-
그 다음은요?
-
tableSize 값으로 나눈
나머지를 구해줍니다
-
이렇게 하면
연결 리스트로 되어 있는 배열에서의
-
인덱스를 알 수 있습니다
-
이렇게 생긴
연결 리스트로 된 배열이 있고
-
어떤 칸은 비어있을 수도 있고
-
어떤 칸에는 하나의 요소가
연결되어 있을 수도 있고
-
하나 이상의 요소가 있는 칸도 있겠죠
-
몇 개의 요소가 들어있는지
우리는 알 수 없고
-
알 필요도 없습니다
-
우리가 알고자 하는 것은
-
찾으려고 하는 키의 위치입니다
-
만약 이 해시가 일반적인 해시처럼
중복된 키를 허용하지 않는다면
-
이 정의에 따라 이 키는
다른 키들과는 다르겠죠
-
여기서 우리가 할 일은
그냥 반복하는 겁니다
-
우리는 이 연결 리스트 내에서
반복적인 작업을 할 겁니다
-
harray[hashval]에서
해시 요소를 하나 꺼냅니다
-
연결 리스트를 만들 때 사용했던
-
반복문을 그대로 사용하는 거죠
-
이것이 바로 우리가
반복문을 쓰는 이유입니다
-
이제 우리가 해야 할 일은
이 첫 번째 요소에 대해서
-
이 요소의 키가 우리가 찾고자 하는
키와 같은지 알아보는 겁니다
-
이 요소에 대해서도
-
우리가 찾으려고 하는 키와
같은 키를 가졌는지 알아봅니다
-
그 다음 요소에 대해서도
-
찾으려고 하는 키와
같은 키를 가졌는지 알아봅시다
-
어떤 방법으로 하면 좋을까요?
-
Comparable을 사용하면 됩니다
-
if문을 쓰고
Comparable을 씁니다
-
이때 우리가 비교하고자 하는 값은
-
해시 요소 E가 아닙니다
-
그 요소의 키를 비교합니다
-
그렇기 때문에 Comparable에
K를 써 줍니다
-
(Comparable<K>)key에
compareTo 함수를 사용해서
-
he.key와 비교하고
-
그 값이 0인지 확인합니다
-
그 결과가 참이 되면
우리가 원하는 상황인 거죠
-
이렇게 되면 이 값을 반환하면 됩니다
-
he.val을 반환합니다
-
여기까지 왔는데도
아직 반환하지 않았다면
-
반환할 것이 없기 때문에
null을 반환합니다
-
이 코드는
지난 몇 주 동안 우리가 배운
-
여러 가지 내용을 합쳐서
만든 겁니다, 그렇죠?
-
Comparable과
비교 키를 사용했고
-
그리고 여기에서는
반복자도 사용했습니다
-
여기에서 사용한 반복자는
-
연결 리스트에서 사용했던 반복자입니다
-
첫 번째 과제에서 힘들게
반복자를 쓰려고 했던 이유는
-
두 번째 과제인 연결 리스트에서
이를 사용할 수 있기 때문입니다
-
hashCode를 사용해서
일정한 시간 내에
-
즉, O(1)로 연결 리스트의
데이터에 접근할 수 있도록 했고
-
이는 기본적으로 여러 연결 리스트의
-
배열을 가지고 있기 때문이었죠
-
그렇기 때문에
어떤 요소든 추가하고 찾고
-
삭제하는 작업을 일정한 시간 내에
수행할 수 있게 됩니다
-
그리고 원하는 만큼 많은 데이터를
-
연결 리스트에 저장할 수 있게 되었죠
-
바로 해시를 이용해서 말입니다