π§· ν΄μ ν μ΄λΈ
μμ νμμΌλ‘λ μκ°μ΄κ³Όμ λΉ μ§κ² λλ λ¬Έμ μμλ ν΄μλ₯Ό μ μ©μμΌ νμ μκ°μ μ€μΌ μ μλ€.
Hash λ λ΄λΆμ μΌλ‘ λ°°μ΄μ μ¬μ©νμ¬ λ°μ΄ν°λ₯Ό μ μ₯νμ¬ μμ λ©λͺ¨λ¦¬λ‘λ νλ‘μΈμ€ κ΄λ¦¬κ° κ°λ₯ν΄μ§κ³ , λΉ λ₯Έ κ²μ μλλ₯Ό κ°λλ€. κ³ μ μ index λ‘ μ κ·Όνμ¬ νΉμ κ°μ νμνκΈ°μ νκ· μ μΌλ‘ μ΄ λλ€.
- μΆ©λ νμμΌλ‘ μΈν΄ "νκ· μ "μΌλ‘ μ΄λ€.
- λ¬Έμ λ μ΄
indexλ‘ μ μ₯λλkeyκ°μ΄ λΆκ·μΉνλ€λ μ μ΄λ€.
μΆ©λ νμ : μλ‘ λ€λ₯Έ λ κ°μ
Keyκ° κ°μindexλ‘ ν΄μ±λμ΄ κ°μ κ³³μ μ μ₯νλ €λ νμ
κ·Έλμ "νΉλ³ν μκ³ λ¦¬μ¦"μ μ¬μ©νμ¬ μ μ₯ν λ°μ΄ν°μ μ°κ΄λ κ³ μ ν μ«μλ₯Ό λ§λ€μ΄ μ΄λ₯Ό index λ‘ μ¬μ©νλ€.
indexλ κ·Έ λ°μ΄ν°λ§μ κ³ μ ν μμΉμ΄λ―λ‘, μ½μ μ΄λ μμ μ°μ° μ μΆκ°μ μΈ λΉμ©μ΄ λ°μνμ§ μλλ€.- μ¬κΈ°μ νΉλ³ν μκ³ λ¦¬μ¦μ
Hash MethodorHash Functionμ΄λΌκ³ νκ³ , μ΄ ν¨μμ μν΄ λ°νλ λ°μ΄ν°μ κ³ μ μ«μ κ°μHash CodeλΌκ³ νλ€. -
νμ§λ§, μλͺ»λ
Hash Functionμ ν΅ν΄ μΆ©λ νμμ΄ λ°μνκ² λ μ μλ€.- μΆ©λ νμμ΄ λ§μμ§μλ‘, νμμ νμν μκ° λ³΅μ‘λλ μ κ°κΉμμ§κ² λλ€.
μ’μ Hash Function μ μΌλ°μ μΌλ‘, Key μ μΌλΆλΆμ μ°Έμ‘°νμ¬ ν΄μ κ°μ λ§λ€μ§ μκ³ , Key μ 체λ₯Ό μ°Έμ‘°νμ¬ ν΄μ κ°μ λ§λ λ€.
- νμ§λ§ μ΄λ
Keyμ νΉμ±μ λ°λΌ λ¬λΌμ§κ² λλ€.
Hash Function μ 무쑰건 1:1 λ§€μΉμΌλ‘ λ§λλ κ²λ³΄λ€, μΆ©λ νμμ μ΅μννλ λ°©ν₯μΌλ‘ μ΄λ₯Ό μ΄λ»κ² λμν κ²μΈκ°κ° λ μ€μνλ€.
- 1:1 λμμ΄ λλλ‘ λ§λλ κ²μ κ±°μ λΆκ°λ₯νκ³ , κ°λ₯νλ€ν΄λ μ΄λ κ³§ λ°°μ΄κ³Ό κ°κΈ°μ λ©λͺ¨λ¦¬ μ¬μ©μ΄ λ§μμ§λ€.
πͺ μΆ©λ νμ ν΄κ²° λ°©λ²
μλ 2κ°μ§ λ°©λ²μ΄ μκ³ , λ λ°©λ² λͺ¨λ μ΅μ μ κ²½μ° μ μκ° λ³΅μ‘λλ₯Ό κ°μ§λ€.
-
Open Address λ°©μ (κ°λ°© μ£Όμλ²) : μΆ©λ νμμ΄ λ°μνλ©΄, (μ¦, μ΄λ―Έ ν΄λΉ ν΄μ λ²ν·μ΄ μ¬μ© μ€μΈ κ²½μ°) λ€λ₯Έ ν΄μ λ²ν·μ μ½μ νλ €λ λ°μ΄ν°λ₯Ό μ½μ νλ λ°©μμ΄λ€.
- μ΄λ, λ°μ΄ν°λ₯Ό μ μ₯νκΈ° μν΄ λΉμ΄ μλ λ€λ₯Έ ν΄μ λ²ν·μ μ°Ύμ ν€λ§¨λ€.
- μ΅μ μ κ²½μ°, λΉμ΄ μλ ν΄μ λ²ν·μ μ°Ύμ§ λͺ»ν΄ λ€μ νμμ μμν μμΉλ‘ λμμ¬ μ μλ€. μ΄λ νμνλ λ°λ μλ 3κ°μ§ λ°©λ²μ΄ μλ€.
-
Linear Probing: μμ°¨μ μΌλ‘ νμνλ λ°©μ
- Primary Clusteringμ μ·¨μ½νλ€.
-
Quadratic Probing: 2μ°¨ ν¨μλ₯Ό μ΄μ©ν΄ νμν μμΉλ₯Ό μ°Ύλλ€. (, , , ... μΌλ‘ νμμμΉ μ¦κ°)
- Secondary Clusteringμ μ·¨μ½νλ€.
-
Double Hashing Probing: νλμ ν΄μ ν¨μμμ μΆ©λμ΄ λ°μνλ©΄ 2μ°¨ ν΄μ ν¨μλ₯Ό μ¬μ©ν΄ νμ¬ μ΄λνμ μ»μ΄ λ€λ₯Έ λ²ν·μ νμνλ€.
- λ μ·¨μ½μ μ ν΄κ²°νμ§λ§, κ°μ₯ λ§μ μ°μ°μ μꡬνλ€.
ν΄μ λ²ν·? : λ°μ΄ν°λ₯Ό μ μ₯νκΈ° μν 곡κ°
-
Separate Chaining λ°©μ (λΆλ¦¬ μ°κ²°λ²) : μΌλ°μ μΌλ‘ Open Addressλ°©μμ Separate Chainingλ³΄λ€ λ리λ€. Open Addressμ κ²½μ° ν΄μ λ²ν·μ μ±μ΄ λ°λκ° λμμ§μλ‘ μ΅μ μ κ²½μ°κ° λ°μν λΉλκ° λμμ§κΈ° λλ¬Έμ΄λ€. λ°λ©΄, Separate Chaining λ°©μμ 보쑰 ν΄μ ν¨μλ₯Ό μ¬μ©ν΄ μ μ‘°μ νλ€λ©΄ μ΅μ μ κ²½μ°μ κ°κΉμμ§λ λΉλλ₯Ό μ€μΌ μ μλ€. Separate Chaining λ°©μμ 2κ°μ§ ꡬν λ°©μμ΄ μλ€.
-
μ°κ²° 리μ€νΈλ₯Ό μ¬μ©νλ λ°©μ (
Linked List)- κ°κ°μ λ²ν·μ μ°κ²° 리μ€νΈλ‘ λ§λ€μ΄ μΆ©λμ΄ λ°μνλ©΄ ν΄λΉ λ²ν·μ listμ μΆκ°νλ λ°©μμ΄λ€.
- μ°κ²° 리μ€νΈμ μ₯, λ¨μ μ κ·Έλλ‘ μ΄μ΄ λ°μ, μμ λλ μ½μ μ΄ κ°λ¨νμ§λ§, μμ λ°μ΄ν°λ€μ μ μ₯ν λ μ°κ²° 리μ€νΈ μ체μ μ€λ²ν€λκ° λ°μνλ€.
- λ²ν·μ κ³μν΄μ μ¬μ©νλ Open Address λ°©μμ λΉν΄ ν μ΄λΈμ νμ₯μ λ¦μΆ μ μλ€λ νΉμ§μ΄ μλ€.
-
Treeλ₯Ό μ¬μ©νλ λ°©μ (
Red-Black Tree)- μ°κ²° 리μ€νΈ λμ νΈλ¦¬λ₯Ό μ¬μ©νλ λ°©μμΌλ‘, μ°κ²° 리μ€νΈλ₯Ό μ¬μ©ν μ§, νΈλ¦¬λ₯Ό μ¬μ©ν μ§ κ²°μ νλ κΈ°μ€μ νλμ ν΄μ λ²ν·μ ν λΉλ
key-valueμμ κ°μμ΄λ€. - νΈλ¦¬μ κΈ°λ³Έμ μΈ λ©λͺ¨λ¦¬ μ¬μ©λμ΄ λ§κΈ° λλ¬Έμ, λ°μ΄ν°μ κ°μκ° μ λ€λ©΄ μ°κ²° 리μ€νΈλ₯Ό μ¬μ©νλ κ²μ΄ ν¨μ¨μ μ΄λ€.
- λ°μ΄ν°μ κ°μκ° μ μ λ, μ±λ₯μμ μ°¨μ΄λ κ±°μ μκΈ°μ λ©λͺ¨λ¦¬μ μΌλ‘ ν¨μ¨μ μΈ μ°κ²° 리μ€νΈλ₯Ό μ¬μ©νλ κ²μ΄ μ’λ€.
- μ°κ²° 리μ€νΈ λμ νΈλ¦¬λ₯Ό μ¬μ©νλ λ°©μμΌλ‘, μ°κ²° 리μ€νΈλ₯Ό μ¬μ©ν μ§, νΈλ¦¬λ₯Ό μ¬μ©ν μ§ κ²°μ νλ κΈ°μ€μ νλμ ν΄μ λ²ν·μ ν λΉλ
-
Java 7μμλ Separate Chaining λ°©μμ μ¬μ©ν΄
HashMapμ ꡬννλ€.
- Open Addressingμ λ°μ΄ν° μμ μ,
remove()μ λΉλ²ν νΈμΆλ‘ μΈν΄ μ²λ¦¬κ° ν¨μ¨μ μ΄κΈ° μ΄λ ΅λ€.- λν, μ μ₯λ ν€-κ° μμ κ°μκ° μΌμ μ΄μμ΄λ©΄, Worst Case λ°μ λΉλκ° λ λμμ Έ Separate Chaining λ°©μλ³΄λ€ λ리λ€.
λ°μ΄ν°κ° μ λ€λ κ²μ μλ―Έ : κΈ°μ€μ μμμ μΈκΈνλ― νλμ ν΄μ λ²ν·μ ν λΉλ
key-valueμμ κ°μμ΄λ€. μ°κ²° 리μ€νΈμ κΈ°μ€κ³Ό νΈλ¦¬μ κΈ°μ€μ 6κ°μ 8κ°λ‘ λλλ€.
- 7μ΄ μλ μ΄μ λ, μλ£κ΅¬μ‘°λ₯Ό λ³κ²½νλ λ° μλͺ¨λλ λΉμ©μ μ€μ΄κΈ° μν¨μ΄λ€.
ν΄μ λ²ν·μ 6κ°μ key-value μμ΄ μλ€κ³ κ°μ ν΄λ³΄μ. μ΄λ νλμ κ°μ΄ μΆκ°λμ΄ μ΄ μμ κ°μκ° 7κ°κ° λμλ€. λ§μ½, κΈ°μ€μ΄ 6, 7μ΄μλ€λ©΄, κ°μ΄ μΆκ°λλ©΄μ μλ£κ΅¬μ‘°λ₯Ό νΈλ¦¬λ‘ λ³κ²½ν΄μΌ νλ€. κ·Έλ¦¬κ³ λ€μ νλμ κ°μ΄ μμ λλ€λ©΄, λ€μ νΈλ¦¬μμ μ°κ²° 리μ€νΈλ‘ μλ£κ΅¬μ‘°λ₯Ό λ³κ²½ν΄μΌ νλ€.
- μ¦, κΈ°μ€μ΄ 1 μ°¨μ΄κ° λλ€λ©΄, μλ£κ΅¬μ‘°λ₯Ό λ³κ²½νλ
SwitchingλΉμ©μ΄ λ무 λ§μ΄ νμνκ² λλ€. - λ°λΌμ, κΈ°μ€μ 2λ§νΌμ μ°¨μ΄λ₯Ό λμλ€.
- κ²°κ³Όμ μΌλ‘, μμ κ°μκ° 6κ° -> 7κ°λ‘ λ³κ²½λλ€λ©΄ μ°κ²° 리μ€νΈ ꡬ쑰λ₯Ό μ μ§ν κ²μ΄κ³ , 8κ° -> 7κ°λ‘ λ³κ²½λλ€λ©΄ νΈλ¦¬ ꡬ쑰λ₯Ό μ μ§ν κ²μ΄λ€.
보쑰 ν΄μ ν¨μ :
keyμ ν΄μ κ°μ λ³ννμ¬ ν΄μ μΆ©λ κ°λ₯μ±μ μ€μ΄κΈ° μν΄ μ¬μ©νλ€. Separate Chaining λ°©μ μ¬μ© μ, ν¨κ» μ¬μ©λλ©° μ΅μ μ κ²½μ°μ κ°κΉμμ§μ§ μλλ‘ νλ€.
πͺ ν΄μ λ²ν· λμ νμ₯ (Resize)
ν΄μ λ²ν·μ κ°μκ° μ λ€λ©΄ λ©λͺ¨λ¦¬ μ¬μ©μ μλ μ μμ§λ§ ν΄μ μΆ©λλ‘ μΈν΄ μ±λ₯ μ μμ€μ΄ λ°μνλ€.
-
κ·Έλμ
HashMapμkey-valueμμ κ°μκ° μΌμ μ΄μμ΄ λλ©΄, ν΄μ λ²ν·μ κ°μλ₯Ό λ λ°°λ‘ λλ¦°λ€. κ°μλ₯Ό λλ¦ΌμΌλ‘μ¨, μΆ©λλ‘ μΈν μ±λ₯ μμ€ λ¬Έμ λ₯Ό μ΄λ μ λ ν΄κ²°ν μ μλ€.- μ¬κΈ°μ μΌμ μ΄μμ μλ―Έλ νμ¬ λ°μ΄ν°μ κ°μκ° ν΄μ λ²ν·μ κ°μμ 75% κ° λ λμ΄λ€.
0.75λΌλ μ«μλ load factorλ‘ λΆλ¦°λ€.
πͺ μμ λ¬Έμ
N(1 ~ 100000)μ κ°λ§νΌ λ¬Έμμ΄μ΄ μ λ ₯λλ€. μ²μ μ λ ₯λλ λ¬Έμμ΄μ "OK", λ€μ΄μ¨ μ μ΄ μλ λ¬Έμμ΄μ "λ¬Έμμ΄ + index"λ‘ μΆλ ₯νλ€.
// input
5
abcd
bac
abcd
abcd
ab
// output
OK
OK
abcd1
abcd2
OK
- Nκ°μ μ΅λ 10λ§μ΄λ―λ‘, μ΄λ₯Ό μμ νμμΌλ‘ ν΄κ²°νλ€λ©΄ μ μκ°λ³΅μ‘λλ₯Ό κ°μ Έ, 100μ΅λ²μ μ°μ°μ΄ νμνλ€. μ΄λ κ³§λ°λ‘ μκ°μ΄κ³Όλ‘ μ΄μ΄μ§ κ²μ΄λ€.
-
λ°λΌμ ν΄μ ν μ΄λΈμ μ΄μ©ν΄ ν΄κ²°ν΄μΌ νλ€.
- μ λ ₯λ λ¬Έμμ΄ κ°μ ν΄μ ν€λ‘ λ³νμμΌ μ μ₯νλ©΄μ μ§ννλ€.
public class Solution {
static final int HASH_SIZE = 1000;
static final int HASH_LEN = 400;
static final int HASH_VAL = 17; // μμλ‘ ν κ², μ£Όλ‘ 17, 19, 23
static String str;
static int N;
static int[][] data = new int[HASH_SIZE][HASH_LEN];
static int[] length = new int[HASH_SIZE];
static String[][] s_data = new String[HASH_SIZE][HASH_LEN];
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(br.readLine()); // μ
λ ₯ μ (1 ~ 100000)
for (int i = 0; i < N; i++) {
str = br.readLine();
// μ
λ ₯ λ¬Έμμ΄λ‘λΆν° ν€ κ°μ μμ±
int key = getHashKey(str);
// ν΄λΉ ν€ κ°μ΄ μ΄λ―Έ μ‘΄μ¬νλμ§ νμΈ
int cnt = checking(key);
// μ΄λ―Έ λ€μ΄μλ λ¬Έμμ΄
if(cnt != -1) sb.append(str).append(cnt).append("\n");
else sb.append("OK").append("\n");
}
System.out.println(sb.toString());
}
public static int getHashKey(String str) {
int key = 0;
// ν€ κ° μμ± (HASH_VAL μ¬μ©)
for (int i = 0; i < str.length(); i++)
key = (key * HASH_VAL) + str.charAt(i) + HASH_VAL;
// ν€ κ° μμλ‘ λ³ν
if(key < 0) key = -key;
return key % HASH_SIZE;
}
public static int checking(int key) {
// νμ¬ ν€μ λ΄κΈ΄ μ
int len = length[key];
// μ΄λ―Έ λ€μ΄μ¨ μ μμ
if(len != 0) {
// μ΄λ―Έ λ€μ΄μ¨ λ¬Έμμ΄μ΄ ν΄λΉ ν€ λ°°μ΄μ μλμ§ νμΈ
for (int i = 0; i < len; i++) {
if(str.equals(s_data[key][i])) {
// μλ€λ©΄ λ€μ΄μ¨ μλ₯Ό λ°ν
data[key][i]++;
return data[key][i];
}
}
}
// λ€μ΄μ¨ μ μ΄ μμμΌλ©΄ ν΄λΉ ν€ λ°°μ΄μ λ¬Έμμ΄μ μ μ₯νκ³ κΈΈμ΄ 1 λ리기
s_data[key][length[key]++] = str;
// λ€μ΄μ¨ μ μμλ€λ©΄ -1 λ°ν
return -1;
}
}