1. 해시(Hash)
1️⃣ 해시란?
어떤 데이터를 고정된 길이의 값(숫자나 문자열)으로 변환한 결과 또는 그 변환 과정(해시 함수)
아무리 큰 데이터라도 “특징만 쏙 뽑아 만든 짧은 요약값”
2️⃣ 해시의 특징
① 해시값의 길이는 항상 일정하다
- 예 : SHA-256 → 항상 256비트 길이의 결과
② 원본을 해시하면 항상 동일한 값이 나온다
③ 충돌할 수 있다
④ 입력이 달라지면 해시값이 크게 달라진다
- 아주 작은 차이만 있어도 완전히 다른 값이 나온다.
⑤ 원래 데이터로 되돌리는 것이 거의 불가능(복호화 불가능)
- 일방향성이 강하다. (특히 보안 해시)
3️⃣ 해시의 목적
데이터가 변했는지 확인하는 용도
예 : 파일의 해시
- 보내기 전:
ABC123
- 받기 후:
ABC123
- 보내기 전과 받은 후가 같으면 → 변조 X
- 보내기 전과 받은 후가 다르면 → 변조 O
➡️ 해시의 핵심 기능은 “데이터가 중간에 바뀌지 않았음을 검증” 하는 것.
4️⃣ 해시는 어디에 쓰일까?
① 빠르게 데이터 찾기 (해시 테이블 / 딕셔너리)
- 키 → 해시값 → 인덱스 계산으로 즉시 접근.
- 예 : Python의 dict, JS의 Object 등.
② 비밀번호 저장
- 비밀번호를 직접 저장하지 않고, 해시값만 저장한다.
③ 파일 무결성 검사
- 파일이 수정되었는지 확인할 때 해시값을 비교한다.
④ 블록체인
- 블록의 데이터와 연결을 유지하기 위해 해시가 활용된다.
5️⃣ 필기 정리
2. 해시코드(Hash Code)
1️⃣ 해시코드란?
어떤 객체(데이터)의 내용을 기반으로 계산한 정수 번호
이 정수를 이용해서 해시테이블에서 빠르게 위치를 찾는 용도로 사용
예:
"apple" → 해시코드 12345678 처럼 정수로 변환.2️⃣ 해시코드의 특징
① 데이터의 내용을 기준으로 계산된다
- 데이터가 같으면 해시코드도 같아야 한다.
※ 동일성 검사 시, hashCode()로 주소 일치여부 먼저 확인 → 주소가 동일하면 값은 무조건 동일
② 데이터 크기와 상관없이 고정된 길이 또는 범위를 가진다.
- Java
hashCode()→ int 범위(32비트)
- SHA-256 → 256비트처럼 길이가 정해져 있다.
③ 빠른 비교·검색에 사용된다
- 예 : 해시테이블, 딕셔너리, 집합(Set)
3️⃣ 해시코드의 원리
① 데이터를 숫자로 바꾼다
문자, 객체, 파일 등 어떤 데이터든 결국 숫자 집합으로 변환할 수 있음
예) 문자열
"abc"'a' = 97
'b' = 98
'c' = 99➡️ 이렇게 데이터의 기본 요소를 숫자로 분해하는 것이 첫 단계
② 숫자들을 조합해 하나의 값으로 압축한다
분해된 숫자들을 특정 규칙으로 섞고 더해서 고정된 크기의 정수 하나로 만듦
대표적인 방식 : Java의 문자열 hashCode() 원리
hash = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
여기서 31 같은 소수를 쓰는 이유
- 값이 고르게 퍼지고
- 충돌을 줄이기 때문
즉, 데이터를 숫자로 바꾸고, 그 숫자들을 비틀어서 하나로 합치는 과정이 해시코드 생성의 핵심 원리
③ 해시테이블에 사용할 때는 인덱스로 변환한다
해시코드는 정수 범위가 매우 크기 때문에 바로 배열 인덱스로 쓰지 않고 다음을 사용
index = hashCode % 배열_크기이렇게 하면
"apple" 같은 데이터가 해시 테이블의 어떤 칸에 저장될지 빠르게 결정할 수 있음package ex06;
public class MyHash03 {
public static void main(String[] args) {
char[] arr = {'A','B','C'};
int h = 0;
// 스탭1. 문자를 숫자로 바꾼다.
int n = arr[0]; // n = 65(A)
h = h * 31 + n; // h = 65
// 스탭2.
n = arr[1]; // n = 66(B)
h = h * 31 + n; // h = 2081
// 스탭3.
n = arr[2]; // n = 67(C)
h = h * 31 + n; // h = 64578 (해시값)
System.out.println(h);
}
}4️⃣ 실습
package ex06;
class Data{ // hashCode 함수는 Object 클래스에 있음 -> extends Object 하지 않아도 디폴트로 들어가 있음(모든 클래스의 부모 Object)
int num;
public Data(int num) {
this.num = num;
}
@Override
public int hashCode() {
return super.hashCode(); // return super.hashCode(); super 최상단 부모클래스(Object)
}
}
public class MyHash extends Object{
public static void main(String[] args) {
Data d1 = new Data(1);
Data d2 = new Data(1); // d1과 d2의 상태는 같지만 주소는 다름 -> 다른 데이터
Data d3 = d1; // 얕은 복사(주소만 복사)
System.out.println(d1.hashCode()); // hashCode는 주소를 반환하는 것
System.out.println(d2.hashCode());
if (d1.hashCode() == d2.hashCode()){
System.out.println("같은 주소에 있는 객체"); // 주소가 같으면 상태(값)도 같음
}else {
System.out.println("다른 주소에 있는 객체"); // 주소 달라도 상태(값)은 같을 수 있음
}
if(d1.num == d2.num){
System.out.println("값이 같습니다.");
}else {
System.out.println("값이 다릅니다.");
}
if(d1.hashCode() == d3.hashCode()){
System.out.println("같아요!! 얕은복사 됐어요");
}else {
System.out.println("달라요!! new가 된 다른 주소 같아요");
}
}
}
※ 오브젝트(Object) 클래스
1) Object 클래스란?
java.lang.Object 클래스 : 모든 클래스의 최상위(super) 클래스Object 클래스는 자바 객체의 공통 조상 클래스로서, 모든 객체가 기본적으로 가져야 하는 최소한의 메서드들을 제공하는 클래스2) Object 클래스가 제공하는 주요 메서드들
①
toString()- 객체를 문자열로 표현할 때 사용
클래스이름@해시코드- 사용자 정의 클래스를 알기 좋은 문자열로 보이게 하고 싶으면 이 메서드를 override해서 사용.
②
equals(Object obj)- 두 객체가 값이 같은지 비교할 때 사용하는 메서드
- 기본 구현은 주소(참조)가 같은지 비교하지만, String, Integer 같은 클래스들은 값을 비교하도록 override 되어 있음.
③
hashCode()- 객체의 해시코드를 반환
- 해시 기반 자료구조(Hashtable, HashMap, HashSet 등)에 필요
equals()를 재정의하면 반드시hashCode()도 함께 재정의해야 함 → 그래야 같은 객체가 같은 해시값을 갖게 됨
④
getClass()- 객체의
Class정보를 반환
- 리플렉션(reflection) 등에 사용
obj.getClass().getName();
⑤
clone()- 객체 복제 기능
Cloneable인터페이스를 구현한 경우에만 사용 가능
3. 해시맵(HashMap)
1️⃣ 해시맵이란?
원하는 값을 “키”를 통해 즉시(O(1)에 가깝게) 찾을 수 있도록 해시 테이블 방식으로 구현된 Map
자바(Java)에서 제공하는 키-값(Key-Value) 기반의 자료구조로,
해시(hash)를 이용해 데이터를 매우 빠르게 저장하고 검색하는 컬렉션
2️⃣ 해시맵의 특징
① 키(Key)는 중복 불가, 값(Value)은 중복 가능
- 같은 키를 넣으면 기존 값이 덮어씌워짐.
- 값은 동일해도 문제 없음.
② 검색 속도가 매우 빠름 (평균 O(1))
- 해시 기반 자료구조이기 때문에
키의 해시코드 → 인덱스 계산 → 해당 버킷에서 값 탐색 과정으로 접근.
③ 순서가 없음
- HashMap은 입력 순서나 정렬 순서를 보장하지 않음.
(순서를 유지하려면 LinkedHashMap 사용)
④ null 키 1개, null 값 여러 개 허용
- 자바 HashMap은 유일하게
null key를 1개 넣을 수 있어.
⑤ 동기화되지 않음 (스레드 안전 X)
- 멀티스레드 환경에서는
ConcurrentHashMap사용.
3️⃣ 해시맵의 동작 원리
1) 배열에 키값 넣기
① 키(Key)의 hashCode() 호출
② 해시코드를 배열의 크기만큼 나눈 나머지 구하기
③ 배열의 나머지 값과 동일한 번지에 put
2) 배열에서 키값 찾기
① 키(Key)의 hashCode() 호출
② 해시코드를 배열의 크기만큼 나눈 나머지 구하기
③ 배열의 나머지 값과 동일한 번지에서 get
※ 충돌이 날 경우,
→ 배열의 크기를 2배 늘려서 재배열 하거나
→ 연결 리스트(Linked List) 사용
4️⃣ 예시
HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 100);
map.put("banana", 200);
System.out.println(map.get("apple")); // 1005️⃣ 실습
package ex06;
import java.util.HashMap;
public class MyHash04 {
public static void main(String[] args) {
HashMap<String, String> arr = new HashMap<>();
arr.put("age","1"); // 크기 1의 배열이 만들어짐 키로 밸류를 찾음
arr.put("name","임꺽정"); // 크기 2의 배열이 만들어짐
System.out.println(arr.get("name"));
}
}
※ 참고 사항
- 데이터를 배열에 담을 때 빈 공간이 생기겠지만 어쩔 수 없음
- 비즈니스에 따라 풀스캔 or 해시맵 선택해야 함
➡️ 해시맵은 검색할 때 필요
➡️ 출석부처럼 1번부터 끝까지 이름 부르는 경우, 풀스캔이 나음
6️⃣ 연결 리스트(Linked List)
1) 연결 리스트란?
데이터들이 줄줄이 손을 잡고 이어져 있는 자료 구조
(각 데이터가 “다음 데이터가 어디 있는지” 주소를 들고 있음)
[데이터1 | 다음노드주소] → [데이터2 | 다음노드주소] → [데이터3 | 다음노드주소]→ 각 칸(노드)이 데이터(data), 다음 노드의 위치(next)를 들고 있는 형태
2) 연결 리스트의 장점
① 중간에 데이터 넣기 쉬움
- 상자 사이에 새로운 상자만 끼워 넣으면 됨
② 크기가 자유롭게 늘어남
- 배열처럼 “칸 부족” 걱정이 없음
3) 연결 리스트의 단점
① 시간이 오래 걸림
- 배열은 번호(index)로 바로 찾아가는 반면, 연결리스트는 맨 처음 노드부터 차례대로 따라가야 함
4) 실습
package ex06;
class Node {
String key;
String value;
Node next;
public Node(String key, String value, Node next) {
this.key = key;
this.value = value;
this.next = next;
}
public void setNext(Node next) {
this.next = next;
}
}
public class MyList01 {
public static void main(String[] args) {
// 1. 첫번째 노드
Node n1 = new Node("name", "홍길동", null);
// 2. 두번째 노드
Node n2 = new Node("age", "11", null);
n1.setNext(n2);
// 3. 세번째 노드
Node n3 = new Node("weight", "50", null);
n2.setNext(n3);
System.out.println(n1.value);
System.out.println(n1.next.value);
System.out.println(n1.next.next.value);
// 4. n2 삭제하기
n1.setNext(n3);
System.out.println(n1.value);
System.out.println(n1.next.value);
System.out.println(n1.next.next.value);
}
}
필기 정리
Share article