ํด์๋ฒ
๐ฌ ํด์๋ฒ์ ๋ฐ์ดํฐ๋ฅผ ์ ์ฅํ ์์น๋ฅผ ๊ฐ๋จํ ์ฐ์ฐ์ผ๋ก ๊ตฌํ๋ ๊ฒ์ผ๋ก, ๊ฒ์๋ฟ๋ง ์๋๋ผ ์ถ๊ฐ, ์ญ์ ๋ ํจ์จ์ ์ผ๋ก ์ํํ ์ ์๋ค.
๐ฌ ์ ๋ ฌ๋ ๋ฐฐ์ด์ ์๋ก์ด ๊ฐ์ ์ถ๊ฐํ๊ธฐ ์ํด์๋ ์๋์ ๊ณผ์ ์ด ํ์ํ๋ค.
๐ฌ ๋ฐฐ์ด์ ํค ๊ฐ์ ๋ฐฐ์ด์ ์์์ 13์ผ๋ก ๋๋ ๋๋จธ์ง๋ก ๋ค์ ๋๋ ๋๋จธ์ง๋ก ์ ๋ฆฌํ๋ฉด ์๋์ ๊ฐ๋ค.
๐ฌ ์ด๋ ๊ฒ ํ์ ์ ๋ฆฌํ ๊ฐ์ ํด์ ๊ฐ์ด๋ผ๊ณ ํ๋ฉฐ, ํด์ ๊ฐ์ ๋ฐ์ดํฐ์ ์ ๊ทผํ ๋ ์ฌ์ฉํ๋ค.
๐ฌ ํด์ ๊ฐ์ด ์ธ๋ฑ์ค๊ฐ ๋๋๋ก ์๋์ ํค ๊ฐ์ ์ ์ฅํ ๋ฐฐ์ด์ด ์๋์ ํด์ ํ ์ด๋ธ์ด๋ค.
๐ฌ ์ด์ ๋ฐฐ์ด์ ์๋ก์ด ๊ฐ 35๋ฅผ ์ถ๊ฐํ ๋, ๋ค๋ฅธ ๋ฐฐ์ด ์์๋ค์ ๋ค๋ก ์ฎ๊ธฐ์ง ์์๋ ๋๋ค.
๐ฌ ์ด์ ๊ฐ์ด ํค ๊ฐ(35)๋ฅผ ๊ฐ์ง๊ณ ํด์ ๊ฐ(9)๋ฅผ ๋ง๋๋ ๊ณผ์ ์ ํด์ ํจ์๋ผ๊ณ ํ๋ฉฐ, ํด์ ํ ์ด๋ธ์ ๊ฐ ์์๋ฅผ ๋ฒํท์ด๋ผ๊ณ ํ๋ค.
์ถฉ๋
๐ฌ ์๋ก์ด ๊ฐ 18์ ์ถ๊ฐํ๋ ๊ฒฝ์ฐ๋ฅผ ์๊ฐํด๋ณด์.
๐ฌ 18์ 13์ผ๋ก ๋๋ ๋๋จธ์ง๊ฐ 5์ด๋ฏ๋ก ์ ์ฅํ ๋ฒํท์ ์ธ๋ฑ์ค๋ 5์ด๋ค.
๐ฌ ํ์ง๋ง, ์๋ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ด ํค ๊ฐ๊ณผ ํด์ ๊ฐ์ ๋์ ๊ด๊ณ๊ฐ ๋ฐ๋์ 1:1์ ์๋์๋ ์๊ธฐ ๋๋ฌธ์ ์ ์ฅํ ๋ฒํท์ด ์ค๋ณต๋๋ ์ถฉ๋ ํ์์ด ๋ฐ์ํ๋ค.
๐ฌ ์ถฉ๋์ ํผํ๊ธฐ ์ํ๊ธฐ ์ํ ์๋์ ๋ ๊ฐ์ง ๋ฐฉ๋ฒ์ ์์๋ณด์.
โฝ ์ฒด์ธ๋ฒ : ๊ฐ์ ํด์ ๊ฐ์ ๊ฐ๋ ์์๋ฅผ ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ก ๊ด๋ฆฌํ๋ค.
โฝ ์คํ ์ฃผ์๋ฒ : ๋น ๋ฒํท์ ์ฐพ์ ๋๊น์ง ํด์๋ฅผ ๋ฐ๋ณตํ๋ค.
์ฒด์ธ๋ฒ
๐ฌ ์ฒด์ธ๋ฒ์ ๊ฐ์ ํด์ ๊ฐ์ ๊ฐ๋ ๋ฐ์ดํฐ๋ฅผ ์ ์ฌ์ฌ ๋ชจ์์ผ๋ก ์ฐ๊ฒฐ ๋ฆฌ์คํธ์์ ์ฐ๊ฒฐํ๋ ๋ฐฉ๋ฒ์ผ๋ก, ์คํ ํด์๋ฒ์ด๋ผ๊ณ ๋ ๋ถ๋ฆฐ๋ค.
๊ฐ์ ํด์ ๊ฐ์ ๊ฐ๋ ๋ฐ์ดํฐ ์ ์ฅํ๊ธฐ
๐ฌ ๋ฐฐ์ด์ ๊ฐ ๋ฒํท์ ์ ์ฅํ๋ ๊ฐ์ ๊ฐ์ ํด์ ๊ฐ์ ๊ฐ๋ ๋ ธ๋๋ฅผ ์ฐ๊ฒฐํ ๋ฆฌ์คํธ์ ์ฒซ ๋ฒ์งธ ๋ ธ๋์ ๋ํ ์ฐธ์กฐ์ด๋ค.
๋ฒํท์ฉ ํด๋์ค Node<K, V>
public class ChainHash<K, V> {
// ํด์๋ฅผ ๊ตฌ์ฑํ๋ ๋
ธ๋
class Node<K, V> {
private K key; // ํค ๊ฐ
private V data; // ๋ฐ์ดํฐ
private Node<K, V> next; // ์ฒด์ธ์ ๋ค์ ๋
ธ๋์ ๋ํ ์ฐธ์กฐ
// ์์ฑ์
Node(K key, V data, Node<K, V> next) {
this.key = key;
this.data = data;
this.next = next;
}
// ํค ๊ฐ์ ๋ฐํ
K getKey() {
return key;
}
// ๋ฐ์ดํฐ๋ฅผ ๋ฐํ
V getValue() {
return data;
}
// ํค์ ํด์ ๊ฐ์ ๋ฐํ
public int hashCode() {
return key.hashCode();
}
}
...
๐ฌ ์ ๋ค๋ฆญ ํด๋์ค Node<K, V>๊ฐ ์ ๋ฌ๋ฐ๋ ๋งค๊ฐ๋ณ์์ ์๋ฃํ์ ํค ๊ฐ์ ์๋ฃํ K์ ๋ฐ์ดํฐ์ ์๋ฃํ V์ด๋ค.
๐ฌ ํ๋ next์ ๋์ ๋๋ ๊ฐ์ ์ฒด์ธ์ ์๋ ๋ค์ ๋ ธ๋์ ๋ํ ์ฐธ์กฐ์ด๋ค.
์์ฑ์ ChainHash
private int size; // ํด์ ํ
์ด๋ธ์ ํฌ๊ธฐ
private Node<K, V>[] table; // ํด์ ํ
์ด๋ธ
// ์์ฑ์
public ChainHash(int capacity) {
try {
table = new Node[capacity];
this.size = capacity;
} catch (OutOfMemoryError e) {
this.size = 0;
}
}
// ํด์ ๊ฐ์ ๊ตฌํจ
public int hashValue(Object key) {
return key.hashCode() % size;
}
๐ฌ ํด๋์ค ChainHash<K, V> ์์ฑ์๋ ํด์ ํ ์ด๋ธ ์ฉ๋(capacity)๋งํผ ๋น์ด ์๋ ํด์ ํ ์ด๋ธ์ ์์ฑํ๋ค.
๐ฌ ์์ฑ์๊ฐ ํธ์ถ๋ ์งํ ๋ฐฐ์ด table์ ๋ชจ๋ ์์๋ null์ ์ฐธ์กฐํ๋ค.
๐ฌ ๋ฉ๋ชจ๋ฆฌ ํ๋ณด์ ์คํจํ๋ฉด(OutOfMemoryError) size์ 0์ ๋ฃ๋๋ค.
ํค ๊ฐ์ผ๋ก ์์๋ฅผ ๊ฒ์ํ๋ search ๋ฉ์๋
// ํค ๊ฐ key๋ฅผ ๊ฐ๋ ์์์ ๊ฒ์ (๋ฐ์ดํฐ๋ฅผ ๋ฐํ)
public V search(K key) {
int hash = hashValue(key); // ๊ฒ์ํ ๋ฐ์ดํฐ์ ํด์ ๊ฐ
Node<K, V> p = table[hash]; // ์ ํ ๋
ธ๋
while (p != null) {
if (p.getKey().equals(key))
return p.getValue(); // ๊ฒ์ ์ฑ๊ณต
p = p.next; // ๋ค์ ๋
ธ๋์ ์ฃผ๋ชฉ
}
return null; // ๊ฒ์ ์คํจ
}
๐ฌ ์๊ณ ๋ฆฌ์ฆ
โป ํด์ ํจ์๊ฐ ํค ๊ฐ์ ํด์ ๊ฐ์ผ๋ก ๋ณํํ๋ค.
โป ํด์ ๊ฐ์ ์ธ๋ฑ์ค๋ก ํ๋ ๋ฒํท์ ์ ํํ๋ค.
โป ์ ํํ ๋ฒํท์ ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ฅผ ์ฒ์๋ถํฐ ์์๋๋ก ๊ฒ์ํ๋ค.
โป ํค ๊ฐ๊ณผ ๊ฐ์ ๊ฐ์ ์ฐพ์ผ๋ฉด ๊ฒ์ ์ฑ๊ณต์ด๋ฉฐ, ๋๊น์ง ์ค์บํ์ฌ ์ฐพ์ง ๋ชปํ๋ฉด ๊ฒ์ ์คํจ์ด๋ค.
์์๋ฅผ ์ถ๊ฐํ๋ Add ๋ฉ์๋
// ํค ๊ฐ key, ๋ฐ์ดํฐ data๋ฅผ ๊ฐ๋ ์์์ ์ถ๊ฐ
public int add(K key, V data) {
int hash = hashValue(key); // ์ถ๊ฐํ ๋ฐ์ดํฐ์ ํด์ ๊ฐ
Node<K, V> p = table[hash]; // ์ ํ ๋
ธ๋
while (p != null) {
if (p.getKey().equals(key)) // ์ด ํค ๊ฐ์ ์ด๋ฏธ ๋ฑ๋ก๋จ
return 1;
p = p.next; // ๋ค์ ๋
ธ๋์ ์ฃผ๋ชฉ
}
Node<K, V> temp = new Node<K, V>(key, data, table[hash]);
table[hash] = temp; // ๋
ธ๋๋ฅผ ์ฝ์
return 0;
}
๐ฌ ์๊ณ ๋ฆฌ์ฆ
โป ํด์ ํจ์๊ฐ ํค ๊ฐ์ ํด์ ๊ฐ์ผ๋ก ๋ณํํ๋ค.
โป ํด์ ๊ฐ์ ์ธ๋ฑ์ค๋ก ํ๋ ๋ฒํท์ ์ ํํ๋ค.
โป ๋ฒํท์ด ๊ฐ๋ฆฌํค๋ ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ฅผ ์ฒ์๋ถํฐ ์์๋๋ก ๊ฒ์ํ๋ค.
โป ํค ๊ฐ๊ณผ ๊ฐ์ ๊ฐ์ ์ฐพ์ผ๋ฉด ํค ๊ฐ์ด ์ด๋ฏธ ๋ฑ๋ก๋ ์ํ์ด๋ฏ๋ก ์ถ๊ฐ์ ์คํจํ๋ค.
โป ๋๊น์ง ์ค์บํ์ฌ ์ฐพ์ง ๋ชปํ๋ฉด ๋ฆฌ์คํธ์ ๋งจ ์ ์์น์ ๋ ธ๋๋ฅผ ์ฝ์ ํ๋ค.
๐ฌ ๋ค์์ ํค ๊ฐ 13๊ณผ 46์ ๊ฐ๋ ๋ ธ๋๋ฅผ ํด์ ํ ์ด๋ธ์ ์ถ๊ฐํ๋ ์์์ด๋ค.
์์๋ฅผ ์ญ์ ํ๋ remove ๋ฉ์๋
// ํค ๊ฐ key๋ฅผ ๊ฐ๋ ์์์ ์ญ์
public int remove(K key) {
int hash = hashValue(key); // ์ญ์ ํ ๋ฐ์ดํฐ์ ํด์ ๊ฐ
Node<K, V> p = table[hash]; // ์ ํ ๋
ธ๋
Node<K, V> pp = null; // ๋ฐ๋ก ์์ ์ ํ ๋
ธ๋
while (p != null) {
if (p.getKey().equals(key)) { // ์ฐพ์ผ๋ฉด
if (pp == null)
table[hash] = p.next;
else
pp.next = p.next;
return 0;
}
pp = p;
p = p.next; // ๋ค์ ๋
ธ๋๋ฅผ ๊ฐ๋ฆฌํจ๋ค.
}
return 1; // ๊ทธ ํค ๊ฐ์ ์๋ค.
}
๐ฌ ์๊ณ ๋ฆฌ์ฆ
โป ํด์ ํจ์๊ฐ ํค ๊ฐ์ ํด์ ๊ฐ์ผ๋ก ๋ณํํ๋ค.
โป ํด์ ๊ฐ์ ์ธ๋ฑ์ค๋ก ํ๋ ๋ฒํท์ ์ ํํ๋ค.
โป ๋ฒํท์ด ๊ฐ๋ฆฌํค๋ ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ฅผ ์ฒ์๋ถํฐ ์์๋๋ก ๊ฒ์ํ๋ค.
โป ํค ๊ฐ๊ณผ ๊ฐ์ ๊ฐ์ ์ฐพ์ผ๋ฉด ๊ทธ ๋ ธ๋๋ฅผ ๋ฆฌ์คํธ์์ ์ญ์ ํ๋ค. ๊ทธ๋ ์ง ์์ผ๋ฉด ์ญ์ ์ ์คํจํ๋ค.
ํด์ ํ ์ด๋ธ์ ๋ชจ๋ ๋ด์ฉ์ ์ถ๋ ฅํ๋ dump ๋ฉ์๋
// ํด์ ํ
์ด๋ธ์ ๋คํ
public void dump() {
for (int i = 0; i < size; i++) {
Node<K, V> p = table[i];
System.out.printf("%02d ", i);
while (p != null) {
System.out.printf("-> %s (%s) ", p.getKey(), p.getValue());
p = p.next;
}
System.out.println();
}
}
๐ฌ ํด์ ํ ์ด๋ธ์ ๋ชจ๋ ์์์ ๋ํ์ฌ ๋ค์์ ์ค๋ ๋ ธ๋๋ฅผ ๋์ด๋น๊ธฐ๋ฉด์ ๊ฐ ๋ ธ๋์ ํค ๊ฐ๊ณผ ๋ฐ์ดํฐ๋ฅผ ์ถ๋ ฅํ๋ ์์ ์ ๋ฐ๋ณตํ๋ค.
์คํ ์ฃผ์๋ฒ
๐ฌ ์ถฉ๋์ด ๋ฐ์ํ์ ๋ ๋ฆฌํด์๋ฅผ ์ํํ์ฌ ๋น์ด ์๋ ๋ฒํท์ ์ฐพ์๋ด๋ ๋ฐฉ๋ฒ์ผ๋ก, ๋ซํ ํด์๋ฒ์ด๋ผ๊ณ ๋ ํ๋ค.
public class OpenHash<K, V> {
// ๋ฒํท์ ์ํ
enum Status {OCCUPIED, EMPTY, DELETED}; // {๋ฐ์ดํฐ ์ ์ฅ, ๋น์ด ์์, ์ญ์ ๋ง์นจ}
// ๋ฒํท
static class Bucket<K, V> {
private K key; // ํค ๊ฐ
private V data; // ๋ฐ์ดํฐ
private Status stat; // ์ํ
// ์์ฑ์
Bucket() {
stat = Status.EMPTY; // ๋ฒํท์ ๋น์ด ์์
}
// ๋ชจ๋ ํ๋์ ๊ฐ์ ์ค์ ํ๋ค.
void set(K key, V data, Status stat) {
this.key = key; // ํค ๊ฐ
this.data = data; // ๋ฐ์ดํฐ
this.stat = stat; // ์ํ
}
// ์ํ๋ฅผ ์ค์
void setStat(Status stat) {
this.stat = stat;
}
// ํค ๊ฐ์ ๋ฐํ
K getKey() {
return key;
}
// ๋ฐ์ดํฐ๋ฅผ ๋ฐํ
V getValue() {
return data;
}
// ํค์ ํด์ ๊ฐ์ ๋ฐํ
public int hashCode() {
return key.hashCode();
}
}
private int size; // ํด์ ํ
์ด๋ธ ํฌ๊ธฐ
private Bucket<K, V>[] table; // ํด์ ํ
์ด๋ธ
// ์์ฑ์
public OpenHash(int size) {
try {
table = new Bucket[size];
for (int i = 0; i < size; i++) {
table[i] = new Bucket<K, V>();
this.size = size;
} catch (OutOfMemoryError e) { // ํ
์ด๋ธ์ ์์ฑํ ์ ์์
this.size = 0;
}
}
// ํด์ ๊ฐ์ ๊ตฌํจ
public int hashValue(Object key) {
return key.hashCode() % size;
}
// ์ฌํด์ ๊ฐ์ ๊ตฌํจ
public int rehashValue(int hash) {
return (hash + 1) % size;
}
// ํค ๊ฐ key๋ฅผ ๊ฐ๋ ๋ฒํท์ ๊ฒ์
private Bucket<K, V> searchNode(K key) {
int hash = hashValue(key); // ๊ฒ์ํ ๋ฐ์ดํฐ์ ํด์ ๊ฐ
Bucket<K, V> p = table[hash]; // ์ ํ ๋ฒํท
for (int i = 0; p.stat != Status.EMPTY && i < size; i++) {
if (p.stat == Status.OCCUPIED && p.getKey().equals(key))
return p;
hash = rehashValue(hash); // ์ฌํด์
p = table[hash];
}
return null;
}
// ํค ๊ฐ key๋ฅผ ๊ฐ๋ ์์์ ๊ฒ์ (๋ฐ์ดํฐ๋ฅผ ๋ฐํ)
public V search(K key) {
Bucket<K, V> p = searchNode(key);
if (p != null)
return p.getValue();
else
return null;
}
// ํค ๊ฐ key, ๋ฐ์ดํฐ data๋ฅผ ๊ฐ๋ ์์์ ์ถ๊ฐ
public int add(K key, V data) {
if (search(key) != null)
return 1; // ์ด ํค ๊ฐ์ ์ด๋ฏธ ๋ฑ๋ก๋จ
int hash = hashValue(key); // ์ถ๊ฐํ ๋ฐ์ดํฐ์ ํด์ ๊ฐ
Bucket<K, V> p = table[hash]; // ์ ํ ๋ฒํท
for (int i = 0; i < size; i++) {
if (p.stat == Status.EMPTY || p.stat == Status.DELETED) {
p.set(key, data, Status.OCCUPIED);
return 0;
}
hash = rehashValue(hash); // ์ฌํด์
p = table[hash];
}
return 2; // ํด์ ํ
์ด๋ธ์ด ๊ฐ๋ ์ฐธ
}
// ํค ๊ฐ key๋ฅผ ๊ฐ๋ ์์์ ์ญ์
public int remove(K key) {
Bucket<K, V> p = searchNode(key); // ์ ํ ๋ฒํท
if (p == null)
return 1; // ์ด ํค ๊ฐ์ ๋ฑ๋ก๋์ง ์์
p.setStat(Status.DELETED);
return 0;
}
// ํด์ ํ
์ด๋ธ์ ๋คํ
public void dump() {
for (int i = 0; i < size; i++) {
System.out.printf("%02d ", i);
switch (table[i].stat) {
case OCCUPIED:
System.out.printf("%s (%s)\n",
table[i].getKey(), table[i].getValue());
break;
case EMPTY:
System.out.println("-- ๋ฏธ๋ฑ๋ก --"); break;
case DELETED:
System.out.println("-- ์ญ์ ๋ง์นจ --"); break;
}
}
}
}
์์ ์ฝ์
๐ฌ ๋ค์์ ์๋ก์ด ๊ฐ 18์ ์ฝ์ ํ๊ณ ์ ํ ๋ ์ถฉ๋์ด ๋ฐ์ํ ๊ฒฝ์ฐ์ด๋ฉฐ, ์ด๋ ๋ฆฌํด์๋ฅผ ์งํํ๋ค.
๐ฌ ๋ฆฌํด์ํ ๋์ ํด์ ๋ฉ์๋๋ ์์ ๋กญ๊ฒ ์ค์ ํ ์ ์์ผ๋ฉฐ, ํด๋น ์์ ์์๋ ํค ๊ฐ์ 1์ ๋ํ ๊ฐ์ 13์ผ๋ก ๋๋ ๋๋จธ์ง๋ก ํ์.
๐ฌ ์์ ๊ฐ์ด ๋น ๋ฒํท์ ๋ง๋ ๋๊น์ง ์ฌํด์๋ฅผ ์ฌ๋ฌ ๋ฒ ๋ฐ๋ณตํ๋ฏ๋ก ์ ํ ํ์ฌ๋ฒ์ด๋ผ๊ณ ๋ ํ๋ค.
์์ ์ญ์
๐ฌ ์ธ๋ฑ์ค๊ฐ 5์ธ ๊ฐ์ ์ญ์ ํ๋ ๊ณผ์ ์ ์ดํด๋ณด๋๋ก ํ์.
๐ฌ ์คํ ์ฃผ์๋ฒ์์๋ ์๋์ ๊ฐ์ ์์ฑ์ ๋ถ์ฌํ์ฌ ์ํ ๊ฐ์ ์ง์ ํ๋๋ก ํ๋ค.
โป ๋ฐ์ดํฐ ์ ์ฅ ์์ฑ๊ฐ
โป ๋น์ด ์์ ์์ฑ๊ฐ(-)
โป ์ญ์ ๋ง์นจ ์์ฑ๊ฐ(โ )
๐ฌ ๋ฐ๋ผ์ 5๋ฅผ ์ญ์ ํ๊ธฐ ์ํด์๋ 5๊ฐ ์์นํ๋ ๊ณณ์ ์ญ์ ๋ฅผ ๋ง์ณค๋ค๋ ์ํ ๊ฐ์ ์ ์ฅํ๋ค.
์์ ๊ฒ์
๐ฌ 17์ ๊ฒ์ํ๋ฉด ํด์ ๊ฐ์ด 4์ธ ๋ฒํท์ด ๋น์ด ์์์ด๋ฏ๋ก ๊ฒ์ ์คํจ์ด๋ค.
๐ฌ 18์ ๊ฒ์ํ๋ฉด ํด์ ๊ฐ์ด 5์ธ ๋ฒํท์ด ์ญ์ ๋ง์นจ์ด๋ฏ๋ก ๋ฆฌํด์๋ฅผ ์ํํ๋ฉฐ, 6์ธ ๋ฒํท์๋ 6์ด ์ ์ฅ๋์ด ์์ผ๋ฏ๋ก ๋ฆฌํด์๋ฅผ ์ํํ๊ณ , 7์ธ ๋ฒํท์์ ์ํ๋ ๊ฐ 18์ ์ฐพ์ ์ ์๋ค.
'Data Structure' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
ํธ๋ฆฌ (0) | 2022.01.03 |
---|---|
์ฐ๊ฒฐ ๋ฆฌ์คํธ (0) | 2021.12.20 |
๋ฌธ์์ด ๊ฒ์ (0) | 2021.12.14 |
๋ฐฐ์ด๋ก ์งํฉ ๋ง๋ค๊ธฐ (0) | 2021.12.13 |
์ฌ๊ท ์๊ณ ๋ฆฌ์ฆ (0) | 2021.11.30 |