조대 협의 블로그 : : ' 자료 구조 ' 태그 의 글 목록 
 ' 자료 구조 ' 에 해당 되 는 글 2 건 
 2016 . 02 . 06 Hashtable 의 이해 와 구현 # 1 ( 6 ) 
 프로그래밍 / 알고리즘 | 2016 . 2 . 6 . 02 : 40 | Posted by 조대 협 
 Hashtable 의 이해 와 구현 # 1 ( 6 ) 
 Mei 2016 . 02 . 06 12 : 57 댓글 주소 수정 / 삭제 댓글 쓰 기 
 Effective Java 책 에 소개 된 Josh Bloch ' s recipe 라는 hash function 만드 는 방법 입니다 . 
 http : / / stackoverflow . com / questions / 113511 / best - implementation - for - hashcode - method 
 shwlinux 2016 . 02 . 11 16 : 21 댓글 주소 수정 / 삭제 댓글 쓰 기 
 hash _ function ( key ) / size _ of _ array 이 부분 오타 같 습니다 ! 
 ff 2016 . 02 . 23 16 : 21 댓글 주소 수정 / 삭제 댓글 쓰 기 
 separate chaining 방식 은 레디스 hashtable 에 도 사용 되 더군요 
 bdjj _ dreamer 2018 . 02 . 08 10 : 16 댓글 주소 수정 / 삭제 댓글 쓰 기 
 출처 : http : / / bcho . tistory . com / 1072 [ 조대 협의 블로그 ] 
 에서 array [ 16 ] 이 아니 라 array [ index ] 로 이해 하 면 되 는 거 겠 죠 ? 
 열 코 2018 . 09 . 07 14 : 59 신고 댓글 주소 수정 / 삭제 댓글 쓰 기 
 공부 하 는 데 많 은 도움 이 됬 습니다 . 
 2019 . 07 . 22 16 : 29 댓글 주소 수정 / 삭제 댓글 쓰 기 
 프로그래밍 / 알고리즘 | 2016 . 2 . 5 . 02 : 52 | Posted by 조대 협 
 Mei 2016 . 02 . 05 20 : 37 댓글 주소 수정 / 삭제 댓글 쓰 기 
 평소 에 블로그 를 잘 보 고 있 는 개발자 입니다 . 
 HashMap 의 table 을 배열 이 아니 라 List 로 만들 게 되 면 , 
 탐색 시간 이 O ( n ) 이 되 기 때문 에 Hash 를 사용 하 는 의미 가 없 어 져 버립니다 . 
 Constant time 에 접근 을 하 기 위해서 는 반드시 배열 을 사용 해야 합니다 . 
 즉 , 이 코드 에서 table 증가 시 array resize 를 하 는 것 은 어쩔 수 없 는 측면 인 것 이 죠 . 
 조대 협 2016 . 02 . 06 01 : 09 신고 댓글 주소 수정 / 삭제 
 HashTable 의 O ( n ) 의 검색 시간 이 나오 지 않 는 것 으로 알 고 있 습니다 . 
 index 의 충돌 이 생겼 을 때 , 충돌 을 해결 하 기 위해서 추가 검색 이 발생 하 고 , Linked List 를 이용 했 을 경우 에 는 n 의 검색 이 소요 됩니다 . 
 실제로 JDK 1 . 8 에서 는 내부 적 으로 index 에 대한 bucket 에 대해서 , List 구조 로 충돌 된 index 의 데 이타 를 사용 하 고 , 해당 index 에 대해서 충돌 데 이타 가 많 을 경우 에 는 Tree 구조 로 바꿔서 저장 하 고 있 습니다 . 
 참고 : http : / / d 2 . naver . com / helloworld / 831311 
 Mei 2016 . 02 . 06 08 : 04 댓글 주소 수정 / 삭제 댓글 쓰 기 
 HashMap 의 table 은 일반 적 으로 이야기 하 는 bucket 이 아닌지요 ? 
 즉 , bucket 탐색 시간 이 constant time ( n 이 아닙니다 ) 이 되 기 위해서 는 array 가 되 어야 하 는 것 이 죠 . 
 동일 hash 를 갖 는 bucket 내부 의 element 들 은 아래 get 함수 를 보 면 아 시 겠 지만 실제로 linked list 입니다 . 
 http : / / grepcode . com / file / repository . grepcode . com / java / root / jdk / openjdk / 6 - b 14 / java / util / HashMap . java # HashMap . get % 28 java . lang . Object % 29 
 kisow 2016 . 02 . 11 19 : 49 댓글 주소 수정 / 삭제 댓글 쓰 기 
 안녕 하 세요 ^^. 저 도 블로그 를 구독 해 보 고 있 는 개발자 입니다 . 
 다양 한 분야 의 좋 은 글 들 많이 읽 고 있 습니다 . 
 매번 읽 기 만 하 다가 관심 있 는 주제 라 글 을 남겨 봅니다 . 
 Mei 님 말씀 처럼 HashTable 의 bucket access 는 자료 구조 특성 상 O ( 1 ) 시간 복잡도 가 요구 되 므로 
 bucket 저장 에 Linked List 자료 구조 는 애당초 의미 가 없 습니다 . chain 방식 이나 open address 방식 에서 
 충돌 을 해결 하 기 위해서 Linked list 유사 하 게 선형 탐색 하 는 부분 은 버킷 크기 가 충분히 큰 경우 어짜피 상수 처리 되 기 때문 에 중요 하 지 않 구요 . 
 HashTable bucket 에서 dynamic array 를 쓰 는 것 은 본문 에 생각 하 신 이유 보다 더 직접 적 으로 는 
 HashTable ADT 에 기대 되 는 시간 복잡도 를 충족 시키 기 위한 제약 사항 에 가깝 습니다 . 
 하지만 본문 의 중심 생각 에 는 100 % 공감 하 고 동의 합니다 . 
 아주 예전 에 acmicpc 준비 하 면서 알고리즘 한참 파 던 때 는 알고리즘 / 자료 구조 의 시간 / 공간 복잡도 가 절대 적 이 라고 생각 했었 는데 , 
 최근 에 10 년 가까이 대용량 데이터 를 다루 다 보 니 항상 그런 것 은 아니 더군요 . 
 N 이 충분히 작 지 않 은 경우 에 도 기존 시공간 복잡도 분석 의 상식 을 뒤엎 을 만큼 성능 에 영향 을 미칠 수 있 는 시스템 상 의 요소 들 이 많 고 , 
 H / W 나 O / S 같 은 하단 인프라 가 발전 하 면서 눈 에 보이 지 않 던 그 영향 이 점점 더 커 지 고 있 습니다 . 
 일 만 PC 나 commodity server 같 은 보편 화 된 환경 에서 특히 더 그런 것 같 고요 . 
 특히 Linked List vs vector ( dynamic array ) 간 의 성능 특성 에 대한 상식 에 논란 이 있 습니다 . 
 몇 년 전 에 Linked List 이제 그만 쓰 고 무조건 vector 쓰 라는 주장 도 나올 정도 로 논란 도 됐었 고요 . 
 극단 적 으로 얘기 해서 그렇 지 최적화 관점 에서 보 면 충분히 의미 있 는 지적 이 라고 생각 합니다 . 
 실제로 저희 도 훨씬 이전 부터 Linked List 를 꼭 써야 하 는 경우 가 아니 면 성능 상 vector 를 쓰 는데 , 꼭 Linked List 를 써야 하 는 경우 가 많 지 않 더군요 . 굳이 꼽 자면 사용자 API 로 덩치 도 크 고 복합 적 인 non - POD 데이터 들 의 목록 을 뽑 아 줄 때 , 성능 은 크 게 중요 하 지 않 고 
 ( 어짜피 튜닝 포인트 도 아니 고 , POD 도 아니 라 어짜피 최적화 도 기대 하 기 힘들 고 ) 
 API 사용 자 들 의 창의 적 인 조합 에 도 리소스 를 덜 써야 하 는 경우 에 만 썼 던 것 같 습니다 . 
 특히 본문 에 언급 하 신 " 불 확실 한 데이터 크기 " 가 유일 한 이유 라면 dynamic array resize 가 더 낫 습니다 . 
 SIMD 나 GPGPU 까지 가 지 않 더라도 아래 와 같 은 이유 때문 에 라도 dynamic array 를 쓰 면서 resize 하 는 게 전체 적 으로 더 효율 적 인 선택 일 수 있 습니다 . 
 추가 하 는 건 원소 가 작 은 POD 라면 복사 비용 자체 도 생각 보다 비싸 지 않 습니다 . 
 게다가 벌크 복사 는 최신 CPU 에 맞 게 컴파일러 가 알 아서 최적화 ( vectorization ) 해줄테 고 , 
 메모리 대역폭 도 거의 정체 된 다른 리소스 들 에 비해서 아직 은 점점 좋 아 지 고 있 고요 . 
 패턴 상 realloc 자체 가 armotized cost 라 항상 치르 는 비용 도 아니 어서 realloc 이 필요 없 는 횟수 만큼 비용 자체 가 분할 상환 될 테 고 
 미리 예상 되 는 만큼 적당히 realloc 해 두 면 효과 를 볼 수 있 어서 
 생각 보다 dynamic array 에서 의 실제 추가 비용 이 떨어지 지 않 을 수 있 습니다 . 
 탐색 비용 은 연속 적 인 array 형태 가 불연속 적 인 Linked List 보다 압도 적 으로 좋 습니다 . 
 알고리즘 상 랜덤 엑세스 가 가능 한 것 도 그렇 지만 순차 탐색 만 놓 고 보 더라도 지역 성 때문 에 array 가 훨씬 좋 습니다 . 
 보통 컴파일러 최적화 수준 에서 데이터 의존 성 이 없 는 경우 에 instruction 수행 순서 를 바꿔서 명령어 수행 의 파이프 라이닝 을 극대 화 하 는 경우 가 많 은데 , 
 노드 를 이동 해 봐야 다음 노드 위치 를 알 수 있 는 Linked List 는 이런 최적화 를 기대 하 기 어렵 습니다 . 
 또 , H / W 레벨 에서 상대 적 으로 느린 메모리 대역폭 을 보완 하 기 위해서 prefetch 할 수 있 는데 
 연속 된 array 는 효과 를 볼 수 있 겠 지만 링크 된 데이터 구조 에서 는 역시 기대 하 기 어렵 습니다 . 
 게다가 Linked List 는 DRAM 과 TLB 의 지역 성 에 도 않 좋 은 영향 을 미치 고 cache 히트 율 을 떨 어 뜨 립 니다 . 
 불연속 적 이 고 더 잦 은 메모리 할당 을 하 는 Linked List 는 리스트 하나 가 여러 DRAM 페이지 에 흩어질 가능 성 이 높 고 
 결과 적 으로 더 많 은 DRAM 페이지 를 요구 하 고 단편 화 도 있 을 테 니 물리 적 인 메모리 usage 도 올라갈 껍니다 . 
 리스트 하나 를 접근 하 는 관점 에서 봐도 사용 하 는 DRAM 페이지 가 많 다는 건 그만큼 지역 성 이 떨어지 고 
 그 자체 로 한정 된 CPU cache 용량 에서 히트 율 자체 에 도 손해 를 볼 테 고요 . 
 현대 O / S 에 보편 적 인 가상 메모리 를 지원 하 기 위해 CPU 에 있 는 TLB 역시 DRAM 페이지 번호 를 찾 기 위한 캐시 인 만큼 
 요구 되 는 DRAM 페이지 가 많 아 지 면 같 은 매 커 니즘 으로 히트 율 손해 를 볼 겁니다 . 
 어떻 게 allocator 를 잘 짜 서 간접 층 을 두 고 실제로 는 연속 적 인 메모리 공간 을 크 게 할당 하 도록 컨트롤 하 면 
 어느 정도 완화 는 되 겠 지만 Linked List 에 만 있 는 링크 자체 도 낭비 고 그렇게 하 는 것 자체 가 크 게 보 면 
 dynamic array resizing 이 고요 . 
 조대 협 2016 . 02 . 12 13 : 55 신고 댓글 주소 수정 / 삭제 댓글 쓰 기 
 의견 감사 드립니다 . 여러 가지 로 생각 하 게 만드 는 의견 이 네요