java에서 HashMap, HashSet, TreeMap, TreeSet 판단 요소가 같은 몇 가지 방법 비교
1.1 HashMap
우선 HashMap에 요소가 어떻게 저장되어 있는지 살펴보자.맵에 저장된 모든 요소는 키-value와 같은 키 값이 맞고put 방법을 통해 추가되며, 같은 키는 맵에 이와 관련된value만 존재합니다.put 방법은 맵에서 다음과 같이 정의됩니다.
V put(K key, V value);
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
HashMap이 원소를 어떻게 저장하는지 알게 된 후에 HashMap이 원소를 어떻게 저장하는지 보면 비교적 간단하다.HashMap에서 원소가 같은지 아닌지를 판단하는 방법은 주로 두 가지가 있는데 하나는 키가 같은지 아닌지를 판단하는 것이고, 하나는value가 같은지 판단하는 것이다.사실 HashMap이 원소를 어떻게 저장하는지 소개할 때 우리는 HashMap이 원소의 키가 같은지 아닌지를 어떻게 판단하는지 소개했다. 그것은 우선hashCode가 같고 그 다음은key가 같거나 equals가 있어야 한다는 것이다.맵에서 키가 같은지 아닌지를 판단하는 것은containsKey () 방법을 통해 이루어진 것으로 HashMap에서 다음과 같이 이루어진다.
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
final Entry<K,V> getEntry(Object key) {
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
맵에서value가 같은지 아닌지를 판단하는 데 사용되는 것은containsValue 방법을 통해 판단하는 것으로 HashMap에서의 실현은 다음과 같다.
public boolean containsValue(Object value) {
if (value == null)
return containsNullValue();
Entry[] tab = table;
for (int i = 0; i < tab.length ; i++)
for (Entry e = tab[i] ; e != null ; e = e.next)
if (value.equals(e.value))
return true;
return false;
}
1.2 HashSet
HashMap이 원소를 어떻게 저장하고 원소가 같은지 판단하는 방식을 알게 된 후에 HashSet이 원소가 같은지 판단하는 방법을 보면 비교적 간단하다.
HashSet의 요소는 사실 HashMap을 통해 저장된다. 모든 HashSet 대상에 대응하는 HashMap 대상의 인용을 가지고 있으며, HashSet에 대한 요소의 추가, 삭제 등 작업을 할 때 HashMap을 통해 진행된다.원소를 저장할 때 대응하는 원소를 가지고 있는 HashMap의 키로 저장하고 대응하는 value는 상량 Object이기 때문에 원소가 같은지 아닌지를 판단할 때 사용하는 것은 HashMap이 키가 같은지 아닌지를 판단하는 논리이다.어떤 요소가 포함되어 있는지 판단할 때도 가지고 있는 HashMap의containsKey 방법을 사용해서 판단합니다.
public boolean contains(Object o) {
returnmap.containsKey(o);
}
1.3 TreeMap
TreeMap에 저장된 요소는 모두 질서정연하고 키에 따라 정렬됩니다.TreeMap은 저장된 요소를 정렬할 때 두 가지 방식이 있는데 하나는 자신이 가지고 있는 Comparator를 통해 정렬하는 것이고, 다른 하나는 Comparable 인터페이스를 실현한 키를 통해 정렬하는 것이다. 첫 번째 방식을 우선적으로 사용하고, 가지고 있는 Comparator(기본값이null)가null일 때 두 번째 방식을 사용한다.TreeMap은 여러 가지 구조 방법으로 가지고 있는 Comparator를 초기화할 수 있습니다.트리맵이 요소를 어떻게 저장하는지 먼저 살펴보겠습니다. 이put 방법은 다음과 같습니다.
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
elseif (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
thrownew NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
elseif (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
thrownew NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
elseif (cmp > 0)
p = p.right;
else
return p;
}
return null;
}
TreeMap의 containsValue의 논리는 역시 판단에 대응하는 value가 equals인지, HashMap과 유사한지, 관심 있는 친구는 TreeMap의 원본을 볼 수 있습니다.
1.4 TreeSet
TreeSet도 Set의 일종의 실현이다. 저장된 요소는 중복되지 않고 질서정연하다. 기본적으로 저장된 요소는 Comparable 인터페이스를 실현해야 한다. 왜냐하면 기본적으로 요소를 Comparable 대상으로 비교하기 때문이다.TreeSet도 Comparator를 통해 그 안에 저장된 요소를 비교할 수 있다. 이것은 TreeSet을 구성할 때 Comparator 대상이나 Comparator 대상을 가진 TreeMap을 전송하여 실현할 수 있다.TreeSet의 실현은 HashSet의 실현과 유사하고 그 내부에도 맵의 인용이 하나 있다. 단지 HashMap이 아니라 TreeMap을 인용할 뿐이다.TreeSet에서 요소의 추가, 삭제 등 조작은 모두 그가 가지고 있는 TreeMap에 의해 이루어진 것이기 때문에 HashSet과 유사하다. TreeSet에서 요소가 같은지 아닌지를 판단하는 방식은 TreeMap과 일치하고 Comparator나 Comparable를 통해 판정하는 것이지 전통적인 equals 방법이 아니다.관심 있는 친구는 트리셋의 원본을 확인해 볼 수 있다.
읽어주셔서 감사합니다. 여러분에게 도움이 되었으면 좋겠습니다. 본 사이트에 대한 지지에 감사드립니다!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[백준 1411] 비슷한 단어 (JAVA)원본 알파벳이 숌하게 바뀔 경우, 이를 HashMap을 이용해서 쌍으로 묶어준다. HashMap 사용법이 익숙하지 못 해서 어려웠던 문제이다. HashMap 사용법 30분 💬 투포인터 버전 참고...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
