HashTable 과 HashMap 은 모두 map 인터페이스의 실현 류 로 이 두 가지 실현 원 리 는 대체적으로 일치 하 며 모두 배열 과 링크 를 바탕 으로 하 는 데이터 구조 이다.
1. 실현 원리:
HashTable 과 HashMap 은 모두 map 인 터 페 이 스 를 실현 했다. 다만 HashTable 은 Dictionary 추상 류 를 계승 하고 HashMap 은 AbstractMap 류 를 계승 했다. 그들의 바 텀 실현 은 대체적으로 일치 하 며 모두 배열 (Entry 유형) 과 링크 등 데이터 구 조 를 바탕 으로 이 루어 진 것 이다.
1. HashTable 과 HashMap 의 구조 방법: 이들 의 구조 방법 은 모두 같 고 다음 과 같은 4 가지 가 있다 (HashMap 을 예 로 들 면)
HashMap() 빈 것 을 만 들 었 다. HashMap ，기본 초기 용량 (16) 과 기본 부하 계수 (0.75).
HashMap(int initialCapacity) 빈 것 을 만 들 었 다. HashMap 은 지정 한 초기 용량 과 기본 부하 인자 (0.75) 를 가지 고 있 습 니 다.
HashMap(int initialCapacity, float loadFactor) 빈 것 을 만 들 었 다. HashMap 은 지정 한 초기 용량 과 부하 인 자 를 가지 고 있 습 니 다.
HashMap(Map extends K,? extends V> m) 새로운 구조 HashMap 은 지정 한 맵 과 같 습 니 다. Map 。
HashMap 의 인 스 턴 스 는 두 개의 성능 에 영향 을 주 는 매개 변수 가 있 습 니 다. 초기 용량
initialCapacity 과 부하 인자
loadFactor. 용량 은 해시 표 의 통 (bucket) 수 이 며, 초기 용량 은 해시 표를 만 들 때의 용량 일 뿐이다. 부하 인 자 는 용량 이 자동 으로 증가 하기 전에 해시 표 가 만족 할 수 있 도록 하 는 도량 이다. 흩 어 진 목록 에 있 는 항목 의 수량 이 부하 인수 와 초기 용량 의 곱 을 초과 하면 해시 표 는 다시 흩 어 집 니 다. (즉, 내부 데이터 구조 가 재 구축 되 었 다) 하 쉬 표 는 통 의 약 두 배 를 가지 게 되 었 다.
일반 규칙 으로서 기본 부하 인자 (.75) 는 시간 과 공간 원가 간 의 좋 은 절충 을 제공 합 니 다. 더 높 은 값 은 공간 비용 을 낮 출 수 있 지만 검색 비용 을 증가 시 킬 수 있 습 니 다 (HashMap 류 의 대부분 작업 에 반영 되 며 get 과 put 를 포함 합 니 다. ）。
HashTable
바 텀 배열 + 링크 가 실현 되 고 key 든 value 든 null 이 될 수 없습니다. 스 레 드 안전 을 실현 하 는 방식 은 데 이 터 를 수정 할 때 전체 HashTable 을 잠 그 는 것 입 니 다. 효율 이 낮 습 니 다. Concurrent HashMap 은 관련 최적화 를 했 습 니 다.
초기 size 11, 확장: newsize = olesize * 2 + 1 index 를 계산 하 는 방법: index = (hash & 0x7FFFFF)% tab. length HashMap
바 텀 배열 + 링크 가 실현 되 고 null 키 와 null 값 을 저장 할 수 있 으 며 스 레 드 가 안전 하지 않 습 니 다 초기 size 16, 확장: newsize = oldsize * 2, size 일정 2 의 n 차 멱 확 대 는 전체 맵 을 대상 으로 확 대 될 때마다 원래 배열 의 요 소 는 순서대로 저장 위 치 를 다시 계산 하고 다시 삽입 한다.
요 소 를 삽입 한 후에 야 확장 해 야 하 는 지 아 닌 지 를 판단 하고 무효 확장 (삽입 후 확장 하지 않 으 면 다시 삽입 하지 않 으 면 무효 확장) Map 에서 요소 의 총수 가 Entry 배열 의 75% 를 초과 하면 확장 작업 을 촉발 하고 링크 의 길 이 를 줄 이기 위해 요소 의 배분 이 더욱 균일 하 다 .
index 계산 방법: index = hash & (tab. length – 1) HashMap 의 초기 값 은 로 딩 인 자 를 고려 해 야 합 니 다:
해시 충돌: 몇몇 Key 의 해시 값 은 배열 크기 에 따라 모드 를 취한 후 같은 배열 아래 에 떨 어 지면 Entry 체인 을 구성 합 니 다. Key 에 대한 검색 은 Entry 체인 의 모든 요 소 를 옮 겨 다 니 며 equals () 를 비교 해 야 합 니 다. 로 딩 인자: 해시 충돌 확률 을 낮 추기 위해 서 는 기본적으로 HashMap 의 키 가 배열 크기 의 75% 에 달 할 때 확장 을 촉발 합 니 다. 따라서 예상 용량 이 100 이면 100 / 0.75 = 134 의 배열 크기 를 설정 해 야 합 니 다. 공간 교환 시간: Key 가 찾 는 시간 을 가속 화하 기 를 원한 다 면 로 딩 인 자 를 더욱 낮 추고 초기 크기 를 늘 려 해시 충돌 확률 을 낮 출 수 있 습 니 다. HashMap 과 Hashtable 은 모두 hash 알고리즘 으로 요소 의 저장 을 결정 하기 때문에 HashMap 과 Hashtable 의 hash 표 는 다음 과 같은 속성 을 포함 합 니 다.
용량 (capacity): hash 표 의 통 수량 초기 화 용량 (initial capacity): hash 표를 만 들 때 통 의 수량, HashMap 은 구조 기 에서 초기 화 용량 을 지정 할 수 있 습 니 다.
사이즈 (size): 현재 hash 표 에 기 록 된 수량 부하 인자 (load factor): 부하 인 자 는 "size / capacity" 와 같 습 니 다. 부하 인 자 는 0 으로 빈 hash 표, 0.5 는 반 만 의 산 목록 을 나타 내 는 것 으로 유추 합 니 다. 가 벼 운 부하 산열 표 는 충돌 이 적 고 삽입 과 조회 에 적합 한 특징 이 있 습 니 다 (단, Iterator 교체 요 소 를 사용 할 때 느 립 니 다) 2. HashMap 과 Hashtable 의 차이
HashMap 과 Hashtable 은 모두 Map 인 터 페 이 스 를 실현 하 였 으 나, 어느 것 을 사용 하기 전에 그 구분 을 먼저 알 아야 할 지 결정 하 였 습 니 다. 주요 한 차이 점 은 스 레 드 안전성, 동기 화 (synchronization), 그리고 속도 입 니 다.
HashMap 은 Hashtable 과 거의 등가 할 수 있 습 니 다. HashMap 이 비 synchronized 인 것 을 제외 하고 null (HashMap 은 null 의 키 (key) 와 값 (value) 을 받 아들 일 수 있 으 며 Hashtable 은 안 됩 니 다. HashMap 은 비 synchronized 이 고 Hashtable 은 synchronized 입 니 다. 이것 은 Hashtable 은 스 레 드 가 안전 하 다 는 것 을 의미 합 니 다. 여러 스 레 드 는 Hashtable 을 공유 할 수 있 습 니 다. 정확 한 동기 화가 없 으 면 여러 스 레 드 는 HashMap 을 공유 할 수 없습니다. 자바 5 는 Concurrent HashMap 을 제공 합 니 다. HashTable 의 대체 로 HashTable 보다 확장 성 이 좋 습 니 다. 또 다른 차이 점 은 HashMap 의 교체 기 (Iterator) 는 fail - fast 교체 기 이 고, Hashtable 의 enumerator 교체 기 는 fail - fast 가 아 닙 니 다. 따라서 다른 스 레 드 가 HashMap 의 구 조 를 바 꾸 었 을 때 (요 소 를 증가 하거나 제거) Concurrent ModificationException 을 던 집 니 다. 그러나 교체 기 자체 의 reove () 는요 소 를 제거 하 는 방법 은 Concurrent ModificationException 이상 을 던 지지 않 습 니 다. 그러나 이것 은 일정한 행동 이 아 닙 니 다. JVM 을 봐 야 합 니 다. 이것 역시 Enumeration 과 Iterator 의 차이 입 니 다. Hashtable 은 스 레 드 가 안전 하고 synchronized 이기 때문에 단일 스 레 드 환경 에서 HashMap 보다 느 립 니 다. 동기 화 할 필요 가 없고 단일 스 레 드 만 필요 하 다 면 HashMap 을 사용 하 는 것 이 Hashtable 보다 성능 이 좋 습 니 다. HashMap 은 시간 이 지 날수 록 Map 의 요소 순서 가 변 하지 않 는 다 고 보장 할 수 없습니다. 우 리 는 HashMap 을 동기 화 할 수 있 습 니까?
HashMap 은 아래 문 구 를 통 해 동기 화 할 수 있 습 니 다. Map m = Collections. synchronizeMap (hashMap);
HashSet 과 HashMap 의 차이
*HashMap*
*HashSet*
HashMap 은 Map 인 터 페 이 스 를 실현 했다.
HashSet 이 Set 인 터 페 이 스 를 실 현 했 습 니 다.
HashMap 저장 키 쌍
HashSet 저장 대상 만
put () 방법 을 사용 하여 요 소 를 map 에 넣 습 니 다.
set 에 요 소 를 add () 방법 으로 넣 기
HashMap 에서 키 대상 을 사용 하여 hashcode 값 을 계산 합 니 다.
HashSet 은 구성원 대상 을 사용 하여 hashcode 값 을 계산 합 니 다. 두 대상 에 게 hashcode 는 같 을 수 있 기 때문에 equals () 방법 은 대상 의 동일성 을 판단 하 는 데 사 용 됩 니 다. 두 대상 이 다 르 면 false 로 돌아 갑 니 다.
HashMap 이 빠 릅 니 다. 유일한 키 로 대상 을 가 져 오기 때 문 입 니 다.
HashSet 은 HashMap 보다 느 려 요.
