해시 테이블은 값을 정수(해시 값) 기반으로 그룹화하여 ‘빈(bin)’에 저장합니다. 값을 찾을 때는 해시 값을 재계산하여 해당 빈으로 바로 이동함으로써 검색 시간을 단축합니다. Ruby에서 해시(my_hash[:key] = "value")에 값을 추가하는 과정은 다음과 같습니다. Ruby는 키와 값을 st_table_entry 구조체에 저장하고, 키의 해시 값을 계산한 후 빈의 개수로 나눈 나머지 값을 사용하여 해당 빈에 엔트리 인덱스를 저장합니다. 예를 들어, :key의 해시 값을 64로 나눈 나머지가 2라면 세 번째 빈(인덱스 2)에 엔트리 인덱스 0을 저장하는 식입니다. 이는 키-값 쌍이 추가된 순서를 유지하는 데도 기여합니다.
값을 검색할 때(p my_hash[:key]), Ruby는 다시 키의 해시 값을 계산하고 빈의 개수로 나눈 나머지를 통해 해당 빈으로 직접 이동합니다. 이 빈에서 저장된 엔트리 인덱스를 찾아 실제 키와 값을 검색합니다. 이러한 방식은 배열이나 연결 리스트를 순회하며 요소를 찾는 것보다 훨씬 빠르며, 요소의 수가 많아질수록 그 효율성은 더욱 두드러집니다.
해시 테이블은 더 많은 값을 수용하기 위해 확장됩니다. Ruby 3.x에서는 오픈 어드레싱(Open Addressing) 방식을 사용하여 해시 충돌을 처리합니다. 이는 충돌 발생 시 다음 사용 가능한 슬롯을 찾아 값을 저장하는 방식으로, 메모리 효율성을 높입니다. 또한, 8개 이하의 엔트리를 가진 작은 해시의 경우, Ruby는 특별한 최적화 방식을 적용하여 성능을 향상시킵니다.
Vladimir Makarov는 2015년에 해시 테이블 코드를 재작성하여 엔트리와 빈 배열을 연속적인 메모리 세그먼트에 저장하도록 했습니다. 이는 최신 CPU가 해시 테이블의 모든 데이터를 더 효율적으로 캐시할 수 있게 하여 전반적인 처리 속도를 높이는 중요한 최적화입니다. 관련 C 코드는 st.c 및 include/ruby/st.h 파일에 있으며, RHash 구조체 정의는 include/ruby/ruby.h에 포함되어 있습니다. 이처럼 Ruby는 해시 테이블의 내부 구현을 지속적으로 개선하여 성능을 극대화하고 있습니다.