김기헌
Hash
Hash는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 갖는다. 그리고 데이터 추가/삭제시 기존 데이터를 밀어내거나 당기는 작업이 필요없도록 특별한 알고리즘을 이용하여 데이터와 연관된 고유한 숫자를 만들어 낸 뒤 이를 인덱스로 사용한다. 특정 데이터가 저장되는 인덱스를 그 데이터만의 고유한 위치로 정하여서 데이터 추가/삭제시 데이터의 이동이 없도록 만들어진 구조이다.
Hash Table
key-value 에서 key를 테이블에 저장할 때 key값을 Hash Method를 이용해 계산을 수행한 후, 그 결과값을 배열의 인덱스로 사용하여 저장하는 방식이다. 여기서 key값을 계산하는 것이 Hash Method 이다.
Hash Method
Hash는 특별한 알고리즘을 이용하여 데이터의 고유한 숫자값을 만들어 인덱스로 사용한다고 했다. 이 알고리즘을 구현한 메소드를 Hash Method라고 하며 Hash Method에 의해 반환된 데이터의 고유 숫자값을 Hash Code 라고한다.
Hash Code
Programmers - 완주하지 못한 선수, 폰켓몬
Hash 응용 문제로 내주신 문제들이다. Hash로는 모두 풀어보았기에 다른 방법으로 해결한 코드이다.
import java.util.Arrays;
class Solution {
public String solution(String[] participant, String[] completion){
String answer="";
Arrays.sort(participant);
Arrays.sort(completion); //두 배열을 정렬하고
for(int i=0;i< completion.length;i++){
if(!participant[i].equals(completion[i])) //정렬된 배열을 앞에서부터 비교한다
return participant[i]; //만약 다른값이 있다면 완주하지 못한 선수이다
}
return participant[participant.length-1];
//완주한 선수의 배열크기만큼 반복문을 실행했기 때문에 끝까지 다른 값이 없었다면
//참가자 배열의 마지막 인원이 완주하지 못한 선수이다
}
}
Java
복사
class Solution {
public int solution(int[] nums) {
int answer = 0,cnt = 0;
int[] arr=new int[200005];
for(int i=0;i<nums.length;i++){
if(arr[nums[i]]==0)answer++; //i번 포켓몬을 잡지 않았을 경우에 ans++
arr[nums[i]]++;//i번 포켓몬의 마리수 check
}
if(answer>=nums.length/2)answer = nums.length/2;
return answer;
}
}
Java
복사
Toby Spring 3장 복습
복습 순서
복습하면서 만났던 오류
김상호
이가현
Hash
F(key) HashCode Index Value
HashCode Index Value•
Hash함수로 HashCode 만들기
public class HashFunction {
public int hash(String key){
int asciiSum=0;
for (int i = 0; i <key.length(); i++ ) {
char c = key.charAt(i);
int ascii =c;
asciiSum += ascii;
System.out.printf("%s %d\n",c,ascii);
}
System.out.println(asciiSum);
return asciiSum%90;
}
public static void main(String[] args) {
HashFunction h = new HashFunction();
h.hash("hello");
}
}
Java
복사
•
HashTable만들기 예제
public class HashTable {
private int size = 10000; //기본 사이즈
public HashTable() {
}
public HashTable(int size) { // 생성자로 사이즈 초기화
this.size = size;
}
public int hash(String key) {
int asciiSum = 0;
for (int i = 0; i < key.length(); i++) {
asciiSum += key.charAt(i);
// System.out.println(asciiSum);
}
return asciiSum % size;
}
public static void main(String[] args) {
String[] names = new String[]{ //이름 생략};
HashTable ht = new HashTable();
Set<Integer> nameSet = new HashSet<>();
for (int i = 0; i < names.length; i++) {
nameSet.add(ht.hash(names[i]));
}
System.out.printf("%s %s\n", names.length, nameSet.size());
}
}
Java
복사
•
insert, search
public class HashTable2 {
private int size = 10000; //기본 사이즈
private int[] table = new int[size];
public HashTable2() {
}
public HashTable2(int size) {
this.size = size;
this.table = new int[size];
}
//1.key 만들어주기
public int hash(String key) {
int asciiSum = 0;
for (int i = 0; i < key.length(); i++) {
asciiSum += key.charAt(i);
}
return asciiSum % 90;
}
//2.table에 key와 value 넣기 (key번째 방에 value넣기)
public void insert(String key, Integer value) {
int hashCode = hash(key); //1번에서 구한 key를 hashcode에 대입
this.table[hashCode] = value; //배열 테이블의 인덱스(key) = value 대입
System.out.println(key + " " + value + "번 방에 저장되었습니다.");
}
public int search(String key) {
return this.table[hash(key)]; // value 리턴
}
public static void main(String[] args) {
String[] names = new String[]{//이름 생략};
HashTable2 ht = new HashTable2(200);
for (int i = 0; i < names.length; i++) {
ht.insert(names[i], ht.hash(names[i]));
}
System.out.println(ht.search("GahyunLee"));
System.out.println(ht.search("JiyoungAhn"));
}
}
Java
복사
