이미 알다시피, 해시에는 키-값 쌍의 데이터를 저장할 수 있는데, 실생활에서 해시와 비슷한 방식을 떠올려 보면 사물함(락커)을 생각해 볼 수 있다.
사물함은 학교, 수영장, 지하철 등 여러 곳에서 볼 수 있는데, 사물함마다 고유 번호와 함께 그 사물함을 열수 있는 키가 있다.
키는 금속 재질로 만들어진 일반적인 키와 RFID 태그를 이용한 키 그리고 번호 키 등 종류가 다양하다.
그리고 일반적으로 사물함 키에는 사물함 번호가 붙어 있는데 키에 붙어 있는 번호의 사물함이 아닌 다른 사물함을 그 키로 열 수는 없다.
사물함이 몇 개 없다면 사물함을 어떤 식으로 배치해 놓더라도 내 키에 해당하는 사물함을 쉽게 찾을 수 있지만, 사물함의 수가 많은 곳에서는 사물함의 배치를 아무렇게나 하면 사용자가 본인의 사물함을 찾는데 애를 먹을 수 있다.
그래서 수영장처럼 사물함의 수가 많은 곳에서는 탈의실 등의 입구에서부터 1~50번, 51~100번, 101~150번처럼 사물함을 번호 구간별로 나눠서 배치해 놓는다.
그래서 내 사물함 키의 번호가 77번이라면 다른 구역은 신경 쓸 필요 없이 51~100번 사물함이 있는 구역으로 들어가서 77번이 붙어 있는 사물함을 찾으면 된다.
77번 사물함을 찾았으면 내가 갖고 있는 키를 사용하여 사물함을 열면 되고, 내가 갖고 있는 키나 사물함 자체에 문제가 없다면 사물함은 잘 열릴 것이다.
해시의 키로 사용할 객체는 값이 변경되지 않는 객체(불변 객체라고 함)가 좋다고 했는데, 사물함 키의 경우도 마찬가지다.
만약 사물함 키가 구리처럼 변형이 잘 되는 금속으로 만들어졌다고 한다면, 해당 사물함을 잘 찾았다고 해도 이미 키가 원래의 모양과 달라져서 사물함을 열 수 없을지도 모른다.
그리고 사물함 키에 붙어 있는 사물함 번호가 수성펜으로 쓰여 있어 물에 번질 경우 식별이 불가능해질 수 있다면, 키의 모양은 변형이 되지 않았다고 해도 사물함 자체를 찾을 수 없을 것이다.
해시는 내부적으로 해시 테이블(Hash Table)이라는 데이터 구조를 사용하여 키-값 쌍의 데이터를 저장하고 관리한다.
그래서 클래스 이름이 Hash이다. 해시 테이블은 키를 통해 생성한 '해시 값'을 사용해서 값을 저장하거나 검색한다.
해시 값은 해시 함수를 통해 계산해낸 값인데, 해시 함수의 입력 값이 같다면 항상 동일한 해시 값을 계산해 돌려줘야 한다.
그렇지 않다면 해시 테이블에 한 번 저장한 값을 다시 찾기 어려울 것이다.
그리고 해시 함수의 입력 값이 조금만 달라져도 완전히 다른 고유한 해시 값을 계산해 돌려줘야 한다.
이것은 보안을 위해 원본 데이터가 위조 또는 변조되지 않았는지 확인하는 작업에 해시 값을 사용할 수 있게 해준다.
또한 해시 테이블은 값을 저장하고 검색하기 위해 키의 해시 값으로부터 생성한 인덱스를 사용하는데, 만약 키의 해시 값들이 서로 비슷해 인덱스가 균등하게 생성되지 못한다면
몇몇 인덱스에만 값들이 모이게 되어 저장 및 검색의 성능이 떨어지게 될 것이다.
아래 그림을 보면 Kernel 모듈에서 hash 메서드를 처음 정의해 놓았고, 기본으로 사용하는 대부분의 클래스에서 hash 메서드를 재정의한 것을 볼 수 있다.
이제 몇 개의 클래스에 대해 hash 메서드를 테스트해보자.
먼저 Kernel 모듈에서 정의해 놓은 hash 메서드를 그대로 사용하는 Object 클래스와 Integer 클래스를 확인해 보자.
아래 그림을 보면 Object 클래스의 경우 생성한 객체마다 hash 메서드의 결괏값이 다르고, Integer 클래스의 객체인 정수의 경우 숫자가 같으면 hash 메서드의 결괏값도 같은 걸 볼 수 있다.
어차피 실행 중인 하나의 루비 프로그램 안에서 똑같은 값을 나타내는 정수(Integer 객체)는 오직 한 개만 존재하기 때문에 Kernel 모듈에서 정의한 hash 메서드는 object_id 메서드처럼 객체마다 다른 값을 돌려주도록 정의해 놓은 것 같다.
irb를 새로 실행하여 앞의 예제 코드를 다시 입력해 보면 정수 1과 2에 대한 hash 메서드의 결괏값이 이전과는 다르지만 여전히 동일한 정수에 대해서는 동일한 결괏값이 나오는 것을 볼 수 있을 것이다.
따라서, 프로그램이 실행 중인 동안 해시에 정수를 키로 하여 저장한 값은 언제라도 같은 정수를 키로 하여 값을 찾을 수 있다.
아래 그림을 보면 str1과 str2가 참조하는 문자열은 서로 다른 객체지만(object_id 값이 다르다) hash 메서드의 결괏값은 같은 걸 볼 수 있다.
만약 String 클래스에서 hash 메서드를 재정의하지 않았다면 해시에 str1을 키로 하여 저장한 값을 str2로는 찾을 수 없었을 것이다.
그리고 앞에서 설명한 대로 문자열이 조금만 달라져도('!') hash 메서드의 결괏값은 많이 다른 것을 볼 수 있다.
우리가 만든 클래스의 객체를 해시의 키로 사용하려면 해당 클래스에서 앞서 설명한 해시 함수의 조건을 충족하도록 hash 메서드를 구현해야 한다.
이미 기본 데이터 타입인 숫자와 문자열 등에서 사용할 수 있는 hash 메서드가 구현되어 있으므로 그것을 사용하여 hash 메서드를 구현하면 된다.
해시의 키로 사용할 수 있는 객체의 클래스를 만들어 보기 전에 해시 클래스와 유사한 나만의 해시 클래스를 직접 만들어보면서 해시에 대한 이해를 높여보자.
아래 MyHash라는 클래스를 정의한 코드가 있다.
먼저 키-값 쌍의 데이터 하나를 보관할 객체를 위해 Entry라는 이름의 클래스를 Struct 클래스를 사용하여 간편하게 정의하였다.
그리고 initialize 메서드에서는 Entry 객체를 저장할 공간에 대한 초기화 작업을 하고 있는데, @bucket_cnt를 10개로 설정하고 그 개수만큼의 빈 배열을 담은 배열을 생성하여 @bucket_list에 할당하였다.
이때 @bucket_list 배열 안의 배열들은 모두 다른 객체여야 하므로 배열 생성 시 블록을 사용하였다.
class MyHash
Entry = Struct.new(:key, :value)
def initialize
@bucket_cnt = 10
@bucket_list = Array.new(@bucket_cnt) { [] }
end
def [](key)
bucket, entry = bucket_and_entry(key)
entry.value if entry
end
def []=(key, value)
bucket, entry = bucket_and_entry(key)
if entry
entry.value = value
else
bucket << Entry.new(key, value)
value
end
end
private
def bucket_and_entry(key)
index = key.hash % @bucket_cnt
bucket = @bucket_list[index]
entry = bucket.find { |e| key.hash == e.key.hash && key.eql?(e.key) }
[bucket, entry]
end
endMyHash 클래스에서 핵심이 되는 bucket_and_entry 메서드는 키를 인수로 받아 해당 키가 저장된(또는 저장될) 공간(bucket)과 함께 실제 그 키로 저장된 데이터(entry)를 찾아 반환해 주는 역할을 한다.
이때 키의 hash 메서드의 결괏값을 @bucket_cnt 값으로 나눈 나머지를 인덱스로 사용하여 버킷을 찾고, 해당 버킷에 저장되어 있는 데이터들과 키를 하나씩 비교해가면서 데이터를 찾는다.
이 로직을 보면 왜 인덱스가 균등하게 생성되어야 하는지 알 수 있다. 그래야 데이터들이 여러 버킷에 고르게 분산되어 저장이 되고 검색 시 키의 비교 횟수가 적어지기 때문이다.
하지만 그렇다 해도 특정 버킷에 데이터가 더 많이 쌓이게 되는 상황은 발생할 수 있는데, 그래서 실제 내부 해시 테이블에서는 버킷의 개수를 늘려 버킷에 저장된 데이터를 다시 고르게 분산하는 작업을 수행한다.
키가 일치하는지 비교할 때는 먼저 두 키의 hash 메서드의 결괏값이 같은지 비교하고 같으면 eql? 메서드를 호출하여 최종 비교를 하도록 했다.
두 객체의 값이 같은지는 보통 == 연산자를 사용하여 비교하는데, eql? 메서드는 == 보다는 조금 더 엄격하게 비교한다.
아래 그림을 보면 정수 1과 실수 1.0을 == 연산자로 비교하면 결과가 true지만 eql? 메서드는 false를 돌려주는 걸 볼 수 있다.
Numeric 클래스에서 eql? 메서드를 객체의 값뿐만 아니라 객체의 클래스도 함께 비교하도록 정의해 놓았기 때문이다.
참고로 equal? 메서드는 두 객체가 동일한 객체인지(object_id가 같은지)를 검사한다.
우리가 해시의 키로 사용할 객체의 클래스를 만들 때는 hash 메서드와 함께 eql? 메서드도 올바르게 구현해 줘야 한다.
그리고 실제 MyHash 클래스의 객체를 생성해서 데이터를 저장하고 조회할 수 있도록 루비의 Hash 클래스처럼 []와 []= 연산자 메서드 두 개를 정의했다.
[] 연산자는 bucket_and_entry 메서드를 통해 키에 대한 데이터(entry)를 조회해 와서 저장된 데이터가 있으면 엔트리 객체의 value 속성값을 반환하고 없으면 nil을 반환한다.
[]= 연산자는 bucket_and_entry 메서드를 통해 키에 해당하는 버킷과 데이터(entry)를 조회해 와서 이미 저장된 데이터가 있으면
엔트리 객체의 value 속성값을 인수로 받은 값으로 변경하고 없으면 인수로 받은 키와 값으로 새로운 엔트리 객체를 생성하여 저장한다.
이제 MyHash 클래스를 테스트해 보기 위해 MyHash 클래스의 코드를 D:/blog/ruby/hash 폴더 아래 my_hash.rb 파일로 저장하자.
그리고 해당 폴더의 위치에서 irb를 실행한 후 아래 그림처럼 코드를 입력해 보면서 결과를 확인해 보자.
루비 해시처럼 MyHash 클래스의 객체를 사용해서도 키-값 쌍의 데이터를 쉽게 저장하고 조회할 수 있는 걸 볼 수 있다.
See you again~~