해싱을 사용하여 지도 구현
- WBOY원래의
- 2024-07-28 07:43:13510검색
해싱을 사용하여 지도를 구현할 수 있습니다. 이제 해싱의 개념을 이해하셨습니다. 해시 테이블의 인덱스에 키를 매핑하기 위해 좋은 해시 함수를 설계하는 방법, 로드 비율을 사용하여 성능을 측정하는 방법, 테이블 크기를 늘리고 성능을 유지하기 위해 재해시하는 방법을 알고 있습니다. 이 섹션에서는 별도의 체이닝을 사용하여 맵을 구현하는 방법을 보여줍니다.
우리는 java.util.Map을 미러링하도록 사용자 정의 Map 인터페이스를 설계하고 인터페이스 이름을 MyMap으로 지정하고 구체적인 클래스 MyHashMap을 지정합니다. , 아래 그림과 같습니다.
MyHashMap을 어떻게 구현하나요? ArrayList를 사용하고 목록 끝에 새 항목을 저장하면 검색 시간은 O(n)이 됩니다. 이진 트리를 사용하여 MyHashMap을 구현하면 트리 균형이 잘 잡혀 있으면 검색 시간은 O(log n)이 됩니다. 그럼에도 불구하고 해싱을 사용하여 MyHashMap을 구현하면 O(1) 시간 검색 알고리즘을 얻을 수 있습니다. 아래 코드는 MyMap 인터페이스
를 보여줍니다.
package demo;
public interface MyMap<K, V> {
/** Remove all of the entries from this map */
public void clear();
/** Return true if the specified key is in the map */
public boolean containsKey(K key);
/** Return true if this map contains the specified value */
public boolean containsValue(V value);
/** Return a set of entries in the map */
public java.util.Set<Entry<K, V>> entrySet();
/** Return the value that matches the specified key */
public V get(K key);
/** Return true if this map doesn't contain any entries */
public boolean isEmpty();
/** Return a set consisting of the keys in this map */
public java.util.Set<K> keySet();
/** Add an entry (key, value) into the map */
public V put(K key, V value);
/** Remove an entry for the specified key */
public void remove(K key);
/** Return the number of mappings in this map */
public int size();
/** Return a set consisting of the values in this map */
public java.util.Set<V> values();
/** Define an inner class for Entry */
public static class Entry<K, V> {
K key;
V value;
public Entry(K key, V value) {
this.key = key;
this.value = value;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
@Override
public String toString() {
return "[" + key + ", " + value + "]";
}
}
}
아래 코드는 별도의 체이닝을 사용하여 MyHashMap을 구현합니다.
package demo;
import java.util.LinkedList;
public class MyHashMap<K, V> implements MyMap<K, V> {
// Define the default hash-table size. Must be a power of 2
private static int DEFAULT_INITIAL_CAPACITY = 4;
// Define the maximum hash-table size. 1 << 30 is same as 2^30
private static int MAXIMUM_CAPACITY = 1 << 30;
// Current hash-table capacity. Capacity is a power of 2
private int capacity;
// Define default load factor
private static float DEFAULT_MAX_LOAD_FACTOR = 0.75f;
// Specify a load factor used in the hash table
private float loadFactorThreshold;
// The number of entries in the map
private int size = 0;
// Hash table is an array with each cell being a linked list
LinkedList<MyMap.Entry<K, V>>[] table;
/** Construct a map with the default capacity and load factor */
public MyHashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_MAX_LOAD_FACTOR);
}
/** Construct a map with the specified initial capacity and
* default load factor */
public MyHashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_MAX_LOAD_FACTOR);
}
/** Construct a map with the specified initial capacity
* and load factor */
public MyHashMap(int initialCapacity, float loadFactorThreshold) {
if(initialCapacity > MAXIMUM_CAPACITY)
this.capacity = MAXIMUM_CAPACITY;
else
this.capacity = trimToPowerOf2(initialCapacity);
this.loadFactorThreshold = loadFactorThreshold;
table = new LinkedList[capacity];
}
@Override /** Remove all of the entries from this map */
public void clear() {
size = 0;
removeEntries();
}
@Override /** Return true if the specified key is in the map */
public boolean containsKey(K key) {
if(get(key) != null)
return true;
else
return false;
}
@Override /** Return true if this map contains the value */
public boolean containsValue(V value) {
for(int i = 0; i < capacity; i++) {
if(table[i] != null) {
LinkedList<Entry<K ,V>> bucket = table[i];
for(Entry<K, V> entry: bucket)
if(entry.getValue().equals(value))
return true;
}
}
return false;
}
@Override /** Return a set of entries in the map */
public java.util.Set<MyMap.Entry<K, V>> entrySet() {
java.util.Set<MyMap.Entry<K, V>> set = new java.util.HashSet<>();
for(int i = 0; i < capacity; i++) {
if(table[i] != null) {
LinkedList<Entry<K, V>> bucket = table[i];
for(Entry<K, V> entry: bucket)
set.add(entry);
}
}
return set;
}
@Override /** Return the value that matches the specified key */
public V get(K key) {
int bucketIndex = hash(key.hashCode());
if(table[bucketIndex] != null) {
LinkedList<Entry<K, V>> bucket = table[bucketIndex];
for(Entry<K, V> entry: bucket)
if(entry.getKey().equals(key))
return entry.getValue();
}
return null;
}
@Override /** Return true if this map contains no entries */
public boolean isEmpty() {
return size == 0;
}
@Override /** Return a set consisting of the keys in this map */
public java.util.Set<K> keySet() {
java.util.Set<K> set = new java.util.HashSet<K>();
for(int i = 0; i < capacity; i++) {
if(table[i] != null) {
LinkedList<Entry<K, V>> bucket = table[i];
for(Entry<K, V> entry: bucket)
set.add(entry.getKey());
}
}
return set;
}
@Override /** Add an entry (key, value) into the map */
public V put(K key, V value) {
if(get(key) != null) { // The key is already in the map
int bucketIndex = hash(key.hashCode());
LinkedList<Entry<K, V>> bucket = table[bucketIndex];
for(Entry<K, V> entry: bucket)
if(entry.getKey().equals(key)) {
V oldValue = entry.getValue();
// Replace old value with new value
entry.value = value;
// Return the old value for the key
return oldValue;
}
}
// Check load factor
if(size >= capacity * loadFactorThreshold) {
if(capacity == MAXIMUM_CAPACITY)
throw new RuntimeException("Exceeding maximum capacity");
rehash();
}
int bucketIndex = hash(key.hashCode());
// Create a linked list for the bucket if not already created
if(table[bucketIndex] == null) {
table[bucketIndex] = new LinkedList<Entry<K, V>>();
}
// Add a new entry (key, value) to hashTable[index]
table[bucketIndex].add(new MyMap.Entry<K, V>(key, value));
size++; // Increase size
return value;
}
@Override /** Remove the entries for the specified key */
public void remove(K key) {
int bucketIndex = hash(key.hashCode());
// Remove the first entry that matches the key from a bucket
if(table[bucketIndex] != null) {
LinkedList<Entry<K, V>> bucket = table[bucketIndex];
for(Entry<K, V> entry: bucket)
if(entry.getKey().equals(key)) {
bucket.remove(entry);
size--; // Decrease size
break; // Remove just one entry that matches the key
}
}
}
@Override /** Return the number of entries in this map */
public int size() {
return size;
}
@Override /** Return a set consisting of the values in this map */
public java.util.Set<V> values() {
java.util.Set<V> set = new java.util.HashSet<>();
for(int i = 0; i < capacity; i++) {
if(table[i] != null) {
LinkedList<Entry<K, V>> bucket = table[i];
for(Entry<K, V> entry: bucket)
set.add(entry.getValue());
}
}
return set;
}
/** Hash function */
private int hash(int hashCode) {
return supplementalHash(hashCode) & (capacity - 1);
}
/** Ensure the hashing is evenly distributed */
private static int supplementalHash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
/** Return a power of 2 for initialCapacity */
private int trimToPowerOf2(int initialCapacity) {
int capacity = 1;
while(capacity < initialCapacity) {
capacity <<= 1; // Same as capacity *= 2. <= is more efficient
}
return capacity;
}
/** Remove all entries from each bucket */
private void removeEntries() {
for(int i = 0; i < capacity; i++) {
if(table[i] != null) {
table[i].clear();
}
}
}
/** Rehash the map */
private void rehash() {
java.util.Set<Entry<K, V>> set = entrySet(); // Get entries
capacity <<= 1; // Same as capacity *= 2. <= is more efficient
table = new LinkedList[capacity]; // Create a new hash table
size = 0; // Reset size to 0
for(Entry<K, V> entry: set) {
put(entry.getKey(), entry.getValue()); // Store to new table
}
}
@Override /** Return a string representation for this map */
public String toString() {
StringBuilder builder = new StringBuilder("[");
for(int i = 0; i < capacity; i++) {
if(table[i] != null && table[i].size() > 0)
for(Entry<K, V> entry: table[i])
builder.append(entry);
}
builder.append("]");
return builder.toString();
}
}
MyHashMap 클래스는 별도의 연결을 사용하여 MyMap 인터페이스를 구현합니다. 해시 테이블 크기와 로드 요소를 결정하는 매개 변수는 클래스에 정의됩니다. 기본 초기 용량은 4(5행)이고 최대 용량은 2^30(8행)입니다. 현재 해시 테이블
용량은 2의 거듭제곱 값으로 설계되었습니다(11행). 기본 부하율 임계값은 0.75f입니다(14행). 지도를 생성할 때 사용자 지정 부하율 임계값을 지정할 수 있습니다. 사용자 정의 부하율 임계값은 loadFactorThreshold(17행)에 저장됩니다. 데이터 필드 size는 지도(라인 20)의 항목 수를 나타냅니다. 해시 테이블은 배열입니다. 배열의 각 셀은 연결 리스트(23행)입니다.
지도 생성을 위해 세 가지 생성자가 제공됩니다. 인수가 없는 생성자(26~28행), 지정된 용량과 기본 부하율 임계값이 있는 맵(32~34행) 및 지정된 용량 및 부하율 임계값으로 매핑합니다(38~46행).
clear 메소드는 지도에서 모든 항목을 제거합니다(49~52행). 버킷의 모든 항목을 삭제하는 removeEntries()를 호출합니다(221~227행). removeEntries() 메서드는 테이블의 모든 항목을 지우는 데 O(용량) 시간이 걸립니다.
containsKey(key) 메서드는 get 메서드(55~60행)를 호출하여 지정된 키가 맵에 있는지 확인합니다. get 메서드는 O(1) 시간이 걸리므로 containsKey(key) 메서드는 O(1) 시간이 걸립니다.
containsValue(value) 메서드는 값이 맵에 있는지 확인합니다(63~74행). 이 방법은 O(용량 + 크기) 시간이 걸립니다. 용량이 7사이즈라서 실제로는 O(용량)입니다.
entrySet() 메서드는 맵의 모든 항목을 포함하는 집합을 반환합니다(77~90행). 이 방법은 O(용량)시간이 소요됩니다.
get(key) 메서드는 지정된 키가 있는 첫 번째 항목의 값을 반환합니다(93~103행). 이 방법은 O(1) 시간이 걸립니다.
isEmpty() 메서드는 맵이 비어 있으면 true를 반환합니다(106~108행). 이 방법은 O(1) 시간이 걸립니다.
keySet() 메서드는 맵의 모든 키를 세트로 반환합니다. 이 메서드는 각 버킷에서 키를 찾아 세트에 추가합니다(111~123행). 이 방법은 O(용량)시간이 소요됩니다.
put(key, value) 메소드는 맵에 새 항목을 추가합니다. 이 메서드는 먼저 키가 이미 맵에 있는지 테스트하고(127행), 그렇다면 항목을 찾아 이전 값을 키 항목의 새 값으로 바꾸고(134행) 이전 값이 반환됩니다( 136행). 키가 맵에서 새로운 것이라면 맵에 새 항목이 생성됩니다(라인 156). 새 항목을 삽입하기 전에 이 메서드는 크기가 부하율 임계값을 초과하는지 확인합니다(라인 141). 그렇다면 프로그램은 rehash()(라인 145)를 호출하여 용량을 늘리고 더 큰 새 해시 테이블에 항목을 저장합니다.
rehash() 메서드는 먼저 세트의 모든 항목을 복사하고(라인 231), 용량을 두 배로 늘리고(라인 232), 새 해시 테이블을 생성하고(라인 233), 크기를 0 (234번째 줄). 그런 다음 메서드는 항목을 새 해시 테이블에 복사합니다(236~238행). rehash 방법은 O(capacity) 시간이 걸립니다. 재해시가 수행되지 않으면 put 메서드는 새 항목을 추가하는 데 O(1) 시간이 걸립니다.
remove(key) 메소드는 맵에서 지정된 키가 있는 항목을 제거합니다(164~177행). 이 방법은 O(1) 시간이 걸립니다.
size() 메서드는 단순히 지도의 크기(180~182행)를 반환합니다. 이 방법은 O(1) 시간이 걸립니다.
values() 메서드는 맵의 모든 값을 반환합니다. 이 메서드는 모든 버킷의 각 항목을 검사하고 이를 세트에 추가합니다(185~197행). 이 방법은 O(용량)시간이 소요됩니다.
hash() 메서드는 supplementalHash를 호출하여 해싱이 균등하게 분산되어 해시 테이블에 대한 인덱스를 생성하도록 합니다(200~208행). 이 방법은 O(1) 시간이 걸립니다.
아래 표에는 MyHashMap에 있는 메서드의 시간 복잡성이 요약되어 있습니다.
재해싱이 자주 발생하지 않으므로 put 방법의 시간 복잡도는 O(1)입니다. clear, entrySet, keySet, values 및 rehash 메소드의 복잡성은 rehash 메소드에 따라 다릅니다. 🎜>용량
, 따라서 이러한 방법의 성능 저하를 방지하려면 초기 용량을 신중하게 선택해야 합니다.아래 코드는 MyHashMap
을 사용하는 테스트 프로그램을 제공합니다.
프로그램은 MyHashMap(7행)을 사용하여 지도를 생성하고 지도에 5개의 항목을 추가합니다(8~12행). 5행에서는 30 값으로 Smith 키를 추가하고 9행에서는 65 값으로 Smith를 추가합니다. 후자의 값이 전자의 값을 대체합니다. 지도에는 실제로 4개의 항목만 있습니다. 프로그램은 맵의 항목을 표시하고(14행), 키 값을 가져오고(16행), 맵에 키와 값이 포함되어 있는지 확인하고(19행), Smith(21행), 지도에 항목을 다시 표시합니다(22행). 마지막으로 프로그램은 지도를 지우고(24행) 빈 지도를 표시합니다(25행).
위 내용은 해싱을 사용하여 지도 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!