โ๊ณต๋ถํ๊ฒ ๋ ๊ณ๊ธฐ
ํ๋ก๊ทธ๋๋จธ์ค ํด์ ํํธ๋ฅผ ํ๊ธฐ ์ ๊ฐ๋ ์ ํ์ธ
โ๏ธ๊ณต๋ถํ ๋ด์ฉ
1๏ธโฃ Hash
โก๏ธ ๊ด๋ จ ์๋ฃ๊ตฌ์กฐ๋ฅผ ์ดํด๋ณด๊ธฐ ์ Hash ์ ๊ฐ๋ ์ ๋ํด์ ์ ํ์๊ฐ ์๋ค.
โ Hash ์ ๋ฑ์ฅ๋ฐฐ๊ฒฝ
โก๏ธ ๋ฐฐ์ด์ ๋ด๋ถ ์ธ๋ฑ์ค๋ฅผ ์ด์ฉํ์ฌ ๊ฒ์์ด ํ๋ฒ์ ์ด๋ฃจ์ด์ ธ ๋น ๋ฅธ ๊ฒ์ ์๋๋ฅผ ๋ณด์ด์ง๋ง, ์ฅ์ &์ฝ์ ์ ๊ณผ์ ์์๋ ๊ทธ๋งํผ ๊ธฐ์กด ์์๋ค์ ์ด๋์์ผ์ผํ๊ธฐ ๋๋ฌธ์ ๋นํจ์จ์ ์ด๋ค.
| ํ์ (Search) | ์ญ์ (Delete) & ์ฝ์ (Insert) |
| O(1) | O(n) |
โก๏ธ ๋งํฌ๋๋ฆฌ์คํธ๋ ์ญ์ &์ฝ์ ์ ๊ณผ์ ์์๋ ๋จ์ ์ฐธ์กฐ ๊ฐ์ ์์ ํ์ฌ ์ฒ๋ฆฌ ๊ฐ๋ฅํ์ง๋ง, ๊ฒ์์ ๊ฒฝ์ฐ ์ฒ์์ด๋ ๋ง์ง๋ง ๋ ธ๋๊ฐ ์๋ ์ด์ ์ํ ๊ฒ์์ ํด์ผํ๊ธฐ ๋๋ฌธ์ ๋นํจ์จ์ ์ด๋ค.
| ํ์ (Search) | ์ญ์ (Delete) & ์ฝ์ (Insert) |
| O(n) | O(1) |
๋ฐฐ์ด๊ณผ ๋งํฌ๋๋ฆฌ์คํธ์ ๊ฐ ํ๊ณ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด ์ ์๋ ๋ฐฉ๋ฒ์ด ํด์ฌ(Hash) ์ด๋ค.
โก Hash ๋?
โก๏ธ ํด์๋ ๋ด๋ถ์ ์ผ๋ก Hash Table ์ด๋ผ๊ณ ํ๋ ๋ฐฐ์ด์ ์ฌ์ฉํ์ฌ ๋ฐ์ดํฐ๋ฅผ ์ ์ฅํ์ฌ ๋น ๋ฅธ ๊ฒ์ ์๋๋ฅผ ๊ฐ์ง๋ฉฐ, ์ฝ์ &์ญ์ ๊ณผ์ ์์๋ ์ผ๋ฐ ๋ฐฐ์ด์ฒ๋ผ ๊ธฐ์กด ๋ฐ์ดํฐ๋ฅผ ์ด๋์ํฌ ํ์๊ฐ ์๊ธฐ ๋๋ฌธ์ ๊ฐํธํ๋ค.
| ํ์ (Search) | ์ญ์ (Delete) & ์ฝ์ (Insert) |
| O(1) | O(1) |
โข Hash Table
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable {
/**
* The hash table data.
*/
private transient Entry<?,?>[] table;
}
โก๏ธ Hash Table ์ ์ ์ค ์๋ถ๋ถ ์ธ๋ฐ ์์์ ์๋ฏธํ ๋ฐฐ์ด์ ์๋ฏธ๋ฅผ ์ ์ ์์ ๊ฒ ๊ฐ์์ ๊ฐ์ง๊ณ ์ ๋ณด์๋ค. Entry ๊ฐ์ฒด๊ฐ ๋ค์ด๊ฐ๋ ๋ฐฐ์ด์ด๋ผ๊ณ ๋ณผ ์ ์๋ค.
โก๏ธ Key ์ Value ๊ฐ ํจ๊ป ์ ์ฅ๋๋ ๊ตฌ์กฐ์ด๋ฉฐ, ์ผ๋ฐ ๋ฐฐ์ด๊ณผ๋ ๋ค๋ฅด๊ฒ ์์ฐจ์ ์ ์ฅ์ด ์๋ ์ ์์ญ์ ๊ณ ๋ฅด๊ฒ ๋ถํฌ๋์ด ์ ์ฅ๋๋ค.
โก๏ธ ์ด๋ Key ๊ฐ์ ์ค๋ณต๋ ์ ์๋ค.

โฃ Hash Method
โก๏ธ ์์์ ์ธ๊ธํ Hash ์ Hash Table ์ ๊ฐ๋ ์ ์ ์ฉํ๊ธฐ ์ํด ํ์ํ ๊ฒ์ด Hash Method ์ด๋ค.
โก๏ธ Hash Table ์ ๊ฒฝ์ฐ ์ ์์ญ์ ๊ณ ๋ฅด๊ฒ ๋ถํฌ๋์ด ์ ์ฅ๋๋ค๊ณ ํ๋๋ฐ hashCode() ๋ฉ์๋๊ฐ ์ด๋ฅผ ์ํด ํ์ฉ๋๋ค. hashCode() ๋ ์ ๋ ฅ๊ฐ์ ์๊ณ ๋ฆฌ์ฆ์ ํตํด ํน์ ๊ธธ์ด์ ์ซ์๊ฐ์ผ๋ก ๋ฐํ์ ์ฃผ๋ ๋ฉ์๋์ด๋ค.
// ์์) Hash Table ์ ํฌ๊ธฐ : 10
String a = "a";
String b = "b";
Stirng c = "c";
int index_a = a.hashCode(); // ๊ฒฐ๊ณผ๊ฐ : 97
int index_b = b.hashCode(); // ๊ฒฐ๊ณผ๊ฐ : 91
int index_c. = c.hashCode(); // ๊ฒฐ๊ณผ๊ฐ : 93
(๊ฒฐ๊ณผ)
a ์ ์ธ๋ฑ์ค : 97 % 10 = 7
b ์ ์ธ๋ฑ์ค : 91 % 10 = 1
c ์ ์ธ๋ฑ์ค : 93 % 10 = 3
โก๏ธ ๊ฒฐ๊ณผ์ ๋ฐ๋ผ ์ธ๋ฑ์ค 1, 3, 7 ์ ์ฐจ๋ก๋๋ก "b", "c", "a" ๊ฐ ๋ด๊ธฐ๊ฒ ๋๋ค. (๊ณ ๋ฅด๊ฒ ๋ถํฌ)
โก๏ธ ์ด ๋ index ์ ์ค๋ณต์ ์ต๋ํ ๋ง๊ธฐ ์ํด์ ๋ฐฐ์ด์ ํฌ๊ธฐ๋ ์์(Pime Number) ๋ก ์ง์ ํ๋ค.
public synchronized V get(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode(); // (1)
int index = (hash & 0x7FFFFFFF) % tab.length; // (2)
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) { // (3)
return (V)e.value;
}
}
return null;
}
โก๏ธ ์ ๋ด์ฉ์ ์ดํดํ๊ณ ๋๋ฉด Hash Table ์ get ๋งค์๋๋ฅผ ์ดํดํ๋ ๊ฒ๋ ์ด๋ ต์ง ์์๊ฒ ๊ฐ๋ค.
1) hash ๊ฐ์ ๊ตฌํ๋ค.
2) ํด๋น ๊ฐ์ ๋ฐฐ์ด์ ํฌ๊ธฐ๋ก ๋๋์ด ๋๋จธ์ง ๊ฐ์ผ๋ก index ๋ฅผ ํ์ธํ๋ค.
3) ํด๋น ์์น์ ์๋ ๊ฐ์ฒด์ hash ๊ฐ์ด ์ฐพ๋ key ์ ํด์ฌ๊ฐ๊ณผ ์ผ์นํ๊ณ ๊ฐ์ฒด๋ ์ผ์นํ๋ฉด ํด๋น value ๊ฐ์ ๋๋ ค์ค๋ค. ์ผ์นํ์ง ์์ผ๋ฉด null
2๏ธโฃ Map
โก๏ธ HashMap ์ ๊ณต๋ถํ๊ธฐ ์ ์ธํฐํ์ด์ค์ธ Map ์ ๋ํด ์ ํ์๊ฐ ์๋ค.
โ ๊ตฌ์กฐ
โก๏ธ ํค (key) ์ ๊ฐ (value) ๋ก ๊ตฌ์ฑ๋ ์ํธ๋ฆฌ (Entry) ๊ฐ์ฒด๋ฅผ ์ ์ฅํ๋ค. ํค์ ๊ฐ์ ๋ชจ๋ ๊ฐ์ฒด์ด๋ฉฐ, ํค๋ ์ค๋ณต ์ ์ฅํ ์ ์์ง๋ง ๊ฐ์ ์ค๋ณต ์ ์ฅํ ์ ์๋ค.

โก๏ธ ๊ธฐ์กด์ ์ ์ฅ๋ ํค์ ๋์ผํ ํค๋ก ๊ฐ์ ์ ์ฅํ๋ฉด ๊ธฐ์กด ๊ฐ์ ์์ด์ง๊ณ , ์๋ก์ด ๊ฐ์ผ๋ก ๋์ฒด๋๋ฉฐ, ํค๋ผ๋ฆฌ ๋๋ ๊ฐ๋ผ๋ฆฌ ๋ฌถ์ด Set ํํ๋ก ๋ฐํ ๊ฐ๋ฅํ๋ค.
โก ๊ตฌํ์ฒด
โก๏ธ Map ์ธํฐํ์ด์ค์ ๋ํ์ ์ธ ๊ตฌํ์ฒด๋ก๋ HashMap, HashTable, TreeMap, Properties ๊ฐ ์๋ค.
3๏ธโฃ HashMap
โ ์ ์ธ
โก๏ธ Map ์ธํฐํ์ด์ค์ ๊ตฌํ์ฒด๋ก์ ์๋์ ๊ฐ์ด ์ ์ธ ๊ฐ๋ฅํ๋ค.
// ์ ์ธ
Map<(key ์ Type), (value ์ Type)> map = new HashMap<>();
// ์์
Map<String, Integer> map = new HashMap<String, Integer>();
Map<String, Integer> map = new HashMap<>();
โก HashMap ์์ ์ค๋ณต key ๊ฐ์ ํ์ธํ๋ ๊ณผ์

โข ์์ ์ฝ๋
import java.util.Map;
import java.uril.HashMap;
public class HashMapExample {
public static void main(String[] src) {
// Map ์ปฌ๋ ์
์์ฑ
Map<String, Integer> map = new HashMap<>();
// (1) ๊ฐ์ฒด ์ ์ฅ
map.push("๊ฐ", 10);
map.push("๋", 20);
map.push("๋ค", 30);
// ์ค๋ณต์ ๋ฐ์ โก๏ธ ๋ฎ์ด์ฐ๊ธฐ
map.push("๊ฐ", 40);
System.out.println(map.size()); // ์ถ๋ ฅ : 3
// (2) ํค๋ก ๊ฐ ์ป๊ธฐ
String key = "๋";
int value = map.get(key);
System.out.println(value); // ์ถ๋ ฅ : 20
// (3) Set ์ปฌ๋ ์
์ป๊ธฐ
Set<String> keySet = map.keySet(); // ํค ๊ฐ๋ง ์กฐํ
Set<Entry<String, Integer>> entrySet = map.entrySet(); // ๋ชจ๋ ์ํธ๋ฆฌ ์กฐํ
}
}
4๏ธโฃ Hash Set
โ ์ ์ธ
โก๏ธ Set ์ธํฐํ์ด์ค์ ๊ตฌํ์ฒด๋ก์ ์๋์ ๊ฐ์ด ์ ์ธ ๊ฐ๋ฅํ๋ค.
// ์ ์ธ
Set<(Type))> set = new HashSet<>();
// ์์
Set<String> set = new HashSet<>();
โก HashMap ์์ ์ค๋ณต๊ฐ์ ํ์ธํ๋ ๊ณผ์

โข ์์ ์ฝ๋
import java.util.HashSet;
public class HashSetExample {
public static void main (String[] args) {
// HashSet ์์ฑ
Set<String> set = new HashSet<>();
// ๊ฐ์ฒด ์ ์ฅ
set.add("Java");
set.add("Python");
set.add("C++");
set.add("Java"); // ์ค๋ณต ๊ฐ์ฒด์ด๋ฏ๋ก ์ ์ฅํ์ง ์์
}
}
โ๏ธ ์ ์ฉ ์์ผ๋ณธ ์์
(์ถ๊ฐ์์ )
๐ง ์ถ๊ฐ๋ก ๊ถ๊ธํ ์
1๏ธโฃ hashCode() ์ equals() ์ ์ฌ์ฉ
โก๏ธ ๊ณต๋ถํ ๋ด์ฉ์ 2๏ธโฃ-โก ๋ถ๋ถ์์ hasCode() ๊ฒฐ๊ณผ๊ฐ๋ง ์ผ์นํ๋ฉด ๋๋ ๊ฒ์ด ์๋๋ผ equals() ๊น์ง ๋ฐํ๊ฐ์ด true ์ฌ์ผ๋ง ์ค๋ณต์ผ๋ก ํ๋จํ๋์ง ๊ถ๊ธํ๋ค. ํด๋น ๋ด์ฉ์ equals ์ hasCode ๋ ์ ๊ฐ์ด ์ฌ์ ์ ํด์ผํ ๊น? ๋ผ๋ ๋ชจ๋ ์๋ฐ ์ธ ์ก์ ์ฑ ๋ด์ฉ์์ ์ ์ ์์๋ค.
๐ ์ฐธ๊ณ
โ ์ด๊ฒ์ด ์๋ฐ๋ค : Ch15-4 Map ์ปฌ๋ ์ ์์ฝ ์์
(https://www.youtube.com/watch?v=y5PJ9YCuDVM&list=PLVsNizTWUw7EmX1Y-7tB2EmsK6nu6Q10q&index=149)
โก Tecoble : equals ์ hashCode ๋ ์ ๊ฐ์ด ์ฌ์ ์ ํด์ผ ํ ๊น?
(https://tecoble.techcourse.co.kr/post/2020-07-29-equals-and-hashCode/)
โข Hash๋ ๋ฌด์์ผ๊น?
'Java ๐งธ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
| (Java) ์คํ(Stack) & ํ(Queue) (0) | 2022.12.31 |
|---|---|
| (Java) ์ฝ์์ ๋ ฅ๋ค์ ์ข ๋ฅ์ ๋น๊ต (InputStream, InputStreamReader, BufferedReader, Scanner) (0) | 2022.10.11 |
| (Java) ๋ฉ์๋_Method (0) | 2022.10.06 |
| (Java) ๊ณต๋ถ์ ๋ชฉ์ (2) | 2022.10.06 |