RAM에 Random이란 단어가 들어가는 이유 / Hash 공부(Java)

계획

오늘 익힌 내용

RAM에는 왜 Random이란 단어가 들어갈까?

일반적으로 보조기억 장치(HDD)는 헤더를 움직여서 원하는 부분을 읽는다. 따라서 이는 순차 접근 메모리라 부른다.

그러나, 메모리의 경우 원하는 데이터가 어디 있든 직접 접근할 수 있다. 따라서 랜덤 접근이라고 한다.

https://www.circuits-diy.com/one-bit-memory-circuit-2/

+) RAM(Random Access Memory)는 전기 신호로 값을 저장한다. 위 그림은 1bit 메모리의 예시인데, 위처럼 전기 신호가 계속 돌면서 저장하는 구조이다.

 

만약 전기 신호가 끊어져 0 값이 계속 들어가게 되면 값이 휘발된다.

 

+) ROM(Read Only Memory)은 바이너리 코드를 사용해 개별 셀에 써 비휘발성 메모리이다. 따라서 펌웨어 등 컴퓨터 부품에 사용된다.

Hash 공부한 내용

해시의 성능을 가장 크게 이끌어내는 방법은 키 전체 크기 만큼의 버켓을 가진 해시 테이블을 만드는 것이다. 이를 Direct Address Table이라 부른다.

 

그러나 이 방법은 메모리 효율이 좋지 않다. 예를 들어 Java의 경우 hashCode()는 int 값을 반환하게 되는데, int는 4바이트이므로, 2^32개의 값을 저장할 수 있는 것이다.

• 여기서 hash_function의 특징은 output의 길이가 항상 같다는 것이다. 또한, 이 길이에 따라 bucket의 크기가 정해진다.

2^32개의 객체를 저장할 일은 극히 드물 것이므로 버켓 크기를 줄여서 사용한다. N보다 작은 수 M으로 나누어 사용한다.

 

int index = X.hashCode() % M;

DAT는 key와 버켓이 1:1 매핑되지만 이 경우에는 (1/M 확률로) 아닐 수도 있다. 이 현상을 hash collision이라 부른다.

hash collision을 해결하는 2가지 방법

https://d2.naver.com/helloworld/831311

Open Addressing : 버킷이 이미 점유중이라면 다른 해시 버켓에 데이터를 삽입한다

• 데이터 저장 / 조회시 Linear Probing, Quadratic Probing 등을 사용한다
• 연속된 공간에 데이터를 저장하기 때문에 캐시 효율이 높다. 데이터 수(M)가 적다면 유용하다.
  • 공간 지역성(Spatial Locality) 특성으로, 특정 메모리 주소에서 데이터를 가져오면 해당 주소 인근의 데이터도 함께 CPU에 로드되기 때문이다.
  • 배열 크기가 커지면 L1, L2 cache hit가 낮아진다.
• Java에서 사용되지 않는 이유는 Open Addressing의 경우 remove()가 빈번히 호출되면 삭제를 효율적으로 하기 어렵기 때문

Separate Chaining : 버킷이 이미 점유중이라면 Linked List로 연결한다 (Java HashMap이 사용)

• HashMap에 저장된 key-value 쌍 수가 일정 개수 이상이면 더 빠르다 (보조 해시로 해시 충돌을 조절할 수 있기 때문)
• 데이터 수가 많아지면 Linked List(N/M) 대신 Red Black Tree(log(N/M))를 사용한다. (Java)

둘 다 worst case에는 O(M)인건 마찬가지이다.

 

추가적으로, Java에서 hashCode()가 재정의된 객체를 자료구조에 값을 넣은 뒤 상태를 변경하면 버킷 주소도 변경될까? 하고 궁금해서 찾아보았더니 변경되지 않는다고 한다. 따라서 이에 따른 문제가 발생할 수 있을 것 같다. 예를 들면, JPA에서 Id만 hashCode()에 넣는 사람들이 가끔 있는 것 같던데, 영속성 컨텍스트에 들어가기 전이라 Id가 null이라 문제가 발생할 수 있을 것 같다.

 

그 밖에도, Map을 다룰 때 hashCode()를 재정의하면 아무래도 기존의 최적화된 해시 함수가 적용되지 않게 되기 때문에 hashCollision이 빈번하게 발생하고 자료구조 성능이 떨어질 것이다.

 

또 하나 생각나는 건, 인턴할 때 HashMap을 사용할 때 크기를 안다면 사이즈를 지정해 주라는 피드백을 받았었다. 처음에는 그냥 아 배열에 값이 일정 수치 이상 들어가면 복제하는 과정이 발생하기 때문에 이를 막으려고 그런 피드백을 주었구나. 하는 생각 뿐이었다.

 

오늘 공부한 내용을 보니, Separate Chaining의 경우 버킷의 크기를 늘리면, 배열을 복사할 뿐만 아니라 Collision이 발생한 값들에 대해 다시 전부 계산해야 하므로 성능이 떨어진다고 한다. 그래서 이러한 의도도 있었구나~ 하고 배워게 되었다.

 

참조

- https://d2.naver.com/helloworld/831311