Hash Table
key - value로 이루어진 자료구조이다.
•
stack만큼 일상적으로 사용된다.
•
Map, Json 등 key, value로 구성되는 모든 자료구조에 쓰인다.
•
Hash Table을 구현하기 위해서는 Hash Function을 알아야 한다.
Hash Function
•
해시 함수는 해시 테이블을 사용하기 위해 필요한 함수이다.
•
해시 함수는 key를 입력받아 고정된 길이의 hash값으로 변경해주는 역할을 한다.
•
해시 함수에서 반환된 hash값이 저장위치가 된다.
Hash Table의 구성
•
key
◦
고유한 값으로 hash function의 input된다.
◦
hash function에 의해 고정된 길이의 해시로 변경된다.
•
hash function
◦
key를 고정된 길이의 hash로 변경해준다.
◦
서로 다른 키를 input 하였는데, 동일한 hash값이 반환될 수 있다. 이를 해시 충돌이라고 부르며, 되도록 피해야 한다.
•
value
◦
배열에 최종적으로 저장되는 값으로, 미리 선언해둔 배열의 hash의 위치에 저장된다.
•
hash table
◦
해시함수를 사용해 key를 hash값으로 매핑하고, hash값을 색인 삼아 value를 key와 함께 저장하는 자료구조이다.
장점과 단점
장점
•
hash table은 key-value가 1:1로 매핑된다. 따라서 자료 삽입, 삭제, 검색 등의 과정에서 평균적으로 O(1)의 시간복잡도를 갖는다. 즉, 속도가 매우 빠르다.
단점
•
해시 충돌이 발생할 수 있다.
•
순서/관계가 있는 배열에는 어울리지 않는다.
•
공간복잡도에서 효율성이 떨어진다. 비어있는 공간이 많이 발생한다.
•
hash function의 의존도가 높다.
Hash의 구현
hash 함수의 예시
public class HashFunction {
public int hash(String key) {
int asciiSum = 0;
for (int i = 0; i < key.length(); i++) {
asciiSum += key.charAt(i);
}
return asciiSum % 90;
}
public static void main(String[] args) {
HashFunction hf = new HashFunction();
hf.hash("chanmin");
}
}
Java
복사
•
이름이 key라고 하자. “chanmin”이 고유한 key로 hash function에 input된다.
•
hash function에서는 “chanmin”을 고유한 int 값으로 변환해 반환한다.
•
chanmin을 int 값으로 반환하는 로직은
◦
모든 문자의 ascii 값을 더한다.
◦
그것을 size(여기서는 90)으로 나눈 나머지를 구한다.
Hash Table의 구현
•
멋사 학생들의 이름이 key이고, hash값이 value라고 하자.
•
총 인원은 87명이다.
•
size는 200으로 정한다.
Hash Table의 연산
•
hash(String key) : key값을 받아서 고유한 hash값을 반환한다.
•
insert(String key, Integer value) : 배열에 hash값의 위치에 value를 저장한다.
•
search(String key) : 배열에 key에 해당하는 value를 찾아 반환한다.
Hash Table의 코드
public class HashTable {
private int size = 200;
private int[] table;
public HashTable() {
this.table = new int[size];
}
public HashTable(int size) {
this.size = size;
this.table = new int[size];
}
public int hash(String key) {
int asciiSum = 0;
for (int i = 0; i < key.length(); i++) {
asciiSum += key.charAt(i);
}
return asciiSum % size;
}
public void insert(String key, Integer value) {
int hashCode = hash(key);
this.table[hashCode] = value;
System.out.println(key + " " + hashCode + " 에 저장이 완료 되었습니다.");
}
public int search(String key) {
return this.table[hash(key)];
}
public static void main(String[] args) {
String[] names = new String[]{"DongyeonKang",
"SubinKang", "KwanwunKo", "HyunseokKo", "KyoungdukKoo", "YeonjiGu", "SoyeonKown", "OhsukKwon", "GunwooKim", "KiheonKim", "NayeongKim", "DohyeonKim", "MinkyoungKim", "MinjiKim", "SanghoKim", "SolbaeKim", "YejinKim", "EungjunKim", "JaegeunKim", "JeonghyeonKim", "JunhoKim", "JisuKim", "kimjinah", "HaneulKim", "HeejungKim", "KimoonPark", "EunbinPark", "JeongHoonPark", "JeminPark", "TaegeunPark", "JiwonBae", "SeunggeunBaek", "JihwanByeon", "HeungseopByeon", "JeongHeeSeo", "TaegeonSeo", "SeeYunSeok", "SuyeonSeong", "SeyoelSon", "MinjiSong", "JinwooSong", "hyunboSim", "SominAhn", "JiyoungAhn", "ChangbumAn", "SoonminEom",
"HyeongsangOh", "SuinWoo", "JuwanWoo", "InkyuYoon", "GahyunLee", "DaonLee", "DohyunLee", "SanghunLee", "SujinLee", "AjinLee", "YeonJae", "HyeonjuLee", "HakjunYim", "SeoyunJang", "SeohyeonJang", "JinseonJang", "SujinJeon", "SeunghwanJeon", "DaehwanJung", "JaeHyunJeung", "HeejunJeong", "GukhyeonCho", "MunjuJo", "YejiJo", "ChanminJu", "MinjunChoi", "SujeongChoi", "SeunghoChoi", "AyeongChoi", "GeonjooHan", "JinhyuckHeo", "MinwooHwang", "SieunHwang",
"JunhaHwang"};
HashTable ht = new HashTable(200);
for (int i = 0; i < names.length; i++) {
ht.insert(names[i], ht.hash(names[i]));
}
System.out.println(ht.search("DongyeonKang"));
System.out.println(ht.search("JiyoungAhn"));
}
}
Java
복사
기타 내용
Size를 정하는 기준
•
어떤 공식이 있는 것은 아니다.
•
Hash 충돌이 나지 않으면서, 메모리를 너무 많이 쓰지 않는 크기를 정한다.
•
ex) 90명이라면 200개 정도
구현한 Hash Table에서 보면
•
10000개를 설정한 경우
◦
실제 인원 : 80 hash 값 개수 : 73
◦
hash 충돌하는 경우가 생기면서도, 메모리를 많이 사용한다.
•
200개를 설정한 경우
◦
실제 인원 : 80 hash 값 개수 : 61
◦
hash 충돌하는 경우가 많다.
hash 충돌의 경우
•
내일 배운다!
Toby’s Spring 3 복습
로컬과 깃허브에 각각 새로운 Repository를 만들고 지금까지 배운 과정을 복습하는 시간을 가졌다.
1. 초난감 DAO와 Test코드
클래스 구성
com
•
dao
◦
UserDao
•
domain
◦
User
test
•
com.dao
◦
UserDaoTest
코드
User
UserDao
UserDaoTest
요약
•
UserDao
◦
add() 메소드가 구현되었다. add() 메소드는 mysql과 연동되어 데이터를 DB에 추가한다.
◦
get() 메소드가 구현되었다. get() 메소드는 mysql과 연동되어 id를 기준으로 데이터를 불러온다.
•
UserDaoTest
◦
addAndGet() 테스트가 구현되었다. 새로운 데이터를 add()한 후, 실제로 그 데이터가 잘 들어갔는지 get()으로 검증한다.
2. Connection의 분리
클래스 구성
com
•
dao
◦
UserDao
◦
ConnectionMaker
◦
AwsConnectionMaker
◦
LocalConnectionMaker
•
domain
◦
User
test
•
com.dao
◦
UserDaoTest
코드
UserDao
UserDaoTest
ConnectionMaker
AwsConnectionMaker
LocalConnectionMaker
요약
•
UserDao
◦
add() 와 get() 메소드에서 중복되던 Connection을 분리했다.
◦
Connection 방법을 생성자로 외부에서 DI할 수 있도록 했다.
•
UserDaoTest
◦
AwsConnectionMaker 객체를 UserDao에 전달하였다.
◦
단, Test코드에서 AwsConnectionMaker 객체를 전달하는 방법은 타당하지 않아 이후 수정된다.
3. DaoFactory 추가, 제어관계 역전
클래스 구성
com
•
dao
◦
UserDao
◦
ConnectionMaker
◦
AwsConnectionMaker
◦
LocalConnectionMaker
◦
DaoFactory
•
domain
◦
User
test
•
com.dao
◦
UserDaoTest
코드
UserDao
UserDaoTest
ConnectionMaker
AwsConnectionMaker
LocalConnectionMaker
DaoFactory
요약
•
DaoFactory
◦
UserDao에 어떤 Connection을 주입할지 결정하는 것을 맡았다.
◦
객체 생성과 객체 주입을 메소드를 분리하였다.
•
UserDaoTest
◦
AwsConnectionMaker 객체를 생성해 UserDao에 전달하던 것을 지웠다.
◦
DaoFactory 객체를 생성하고 이 객체를 참조해 DaoFactory 내부 메소드로 UserDao에 Connection 객체를 주입하였다
4. 스프링 IoC 사용
클래스 구성
com
•
dao
◦
UserDao
◦
ConnectionMaker
◦
AwsConnectionMaker
◦
LocalConnectionMaker
◦
DaoFactory
•
domain
◦
User
test
•
com.dao
◦
UserDaoTest
코드
UserDao
DaoFactory
ConnectionMaker
AwsConnectionMaker
LocalConnectionMaker
UserDaoTest
요약
•
DaoFactory
◦
Spring을 활용하기 위해 어노테이션을 추가했다.
◦
@Configuration, @Bean을 클래스와 메소드 상단에 작성했다.
•
UserDaoTest
◦
Applicationcontext에서 객체를 주입받았다.
◦
UserDao userDao = context.getBean("awsUserDao", UserDao.class); 코드를 통해 “awsUserDao” 이름의 메소드로 UserDao.class를 불러온다. 이때 UserDao는 AwsConnectionMaker의 객체를 주입받는다.
5. DataSource 사용
클래스 구성
com
•
dao
◦
UserDao
◦
DaoFactory
•
domain
◦
User
test
•
com.dao
◦
UserDaoTest
코드
UserDao
DaoFactory
UserDaoTest
개념
DataSource
•
자바에서 제공하는 인터페이스로 DB 커넥션을 가져오는 기능을 제공한다.
•
getConnection() 메소드는 DB 커넥션을 가져온다.
•
기타 다양한 메소드가 있다.
요약
•
DaoFactory
◦
기존의 만들었던 ConnectionMaker의 그 구현 클래스들을 사용하지 않고 DataSource를 사용하였다.
•
UserDaoTest
◦
기존에 UserDao는 AwsConnectionMaker의 객체를 주입받았지만, 생성자와 멤버변수를 DataSource 객체를 주입받도록 코드를 수정하였다. getBean() 메소드에 의해 awsDataSource()이 실행되고 UserDao는 DataSource 객체를 주입받는다.
•
ConnectionMaker 인터페이스와 그 구현 클래스들을 삭제하였다.
6. getCount(), deleteAll() 메소드 추가
클래스 구성
com
•
dao
◦
UserDao
◦
DaoFactory
•
domain
◦
User
test
•
com.dao
◦
UserDaoTest
코드
UserDao
DaoFactory
UserDaoTest
개념
@BeforeEach
•
@BeforeEach : 이 어노테이션을 붙이면 그 메소드는 Test 메소드가 실행되기 전에 수행된다. Test 전체 클래스가 아닌, 개별 Test 메소드를 실행하였을 때도 @BeforeEach 는 수행된다.
Junit 메소드
•
assertThrows()
◦
특정 예외가 발생하였는지 확인
◦
첫 번째 인자는 확인할 예외 클래스
◦
두 번째 인자는 테스트 하려는 코드
요약
•
UserDao
◦
deleteAll(), getCount() 메소드를 추가하였다.
•
UserDaoTest
◦
추가한 메소드를 검증하기 위해 Test 코드를 작성하였다.
◦
@BeforeEach 메소드를 활용해 Test 코드 작성 시 사용할 객체들을 정리하였다.
◦
모든 test에서 deleteAll()을 사용해 test 때마다 DB가 비어있을 수 있도록 하였다. 이를 통해 테스트 결과가 일관적으로 나올 수 있도록 했다.
◦
getUserFailure() test에는 get() 메소드에서 발생할 수 있는 예외를 테스트하였다. get() 메소드는 DB에 존재하지 않는 id를 입력받으면 EmptyResultDataAccessException 예외를 발생시킨다. assertThrows()를 통해 이러한 예외가 잘 발생하는지 테스트 할 수 있다.
7. 예외처리
클래스 구성
com
•
dao
◦
UserDao
◦
DaoFactory
•
domain
◦
User
test
•
com.dao
◦
UserDaoTest
코드
UserDao
DaoFactory
UserDaoTest
요약
•
UserDao
◦
deleteAll(), getCount() 메소드에 try/catch/finally 구문을 적용해 예외처리를 해주었다.
◦
기존에는 오류 발생 시 Connection을 반환하지 못했다면, 예외처리 후 finally 구문을 통해 Connection을 반환할 수 있도록 하였다.
8. 전략 패턴
클래스 구성
com
•
dao
◦
UserDao
◦
DaoFactory
◦
StatementStrategy
◦
DeleteAllStatement
◦
AddStatement
•
domain
◦
User
test
•
com.dao
◦
UserDaoTest
코드
UserDao
DaoFactory
StatementStrategy
AddStatement
DeleteAllStatement
UserDaoTest
개념
전략패턴
전략패턴은 변하지 않는 어떤 맥락(Context)에서 변하는 부분(Strategy)만 따로 정의하고 기능을 수행하도록 하는 디자인 패턴이다.
•
변하지 않는 맥락(context)는 jdbcContextWithStatementStrategy() 메소드에 담았다.
•
변하는 전략(Strategy)은 add(), deleteAll() 메소드 등의 기능을 수행하기 위한 쿼리문의 차이 등이다.
•
add(), deleteAll() 메소드 등의 기능을 수행하기 위한 전략은 AddStatement, DeleteAllStatement 등의 클래스에 담겨 있다.
•
add(), deleteAll() 메소드는 이러한 전략을 객체로 생성하고, jdbcContextWithStatementStrategy() 메소드에 전달하여, 자신의 기능을 수행한다.
요약
•
UserDao
◦
jdbcContextWithStatementStrategy() 메소드가 추가되었다. 기존에 add(), deleteAll() 메소드에서 중복되던 내용을 담고 있다.
◦
add(), deleteAll() 메소드는 AddStatement, DeleteAllStatement 객체를 각각 생성하고 이 객체를 jdbcContextWithStatementStrategy()에 전달하여 호출한다.
•
Strategy
◦
StatementStrategy 인터페이스로 makePreparedStatement() 메소드를 갖고 있다.
◦
AddStatement, DeleteAllStatement는 StatementStrategy 인터페이스의 구현 클래스이다. makePreparedStatement() 메소드를 오버라이드함으로써 add(), deleteAll() 기능에 필요한 SQL 구문과 설정을 담고 있다.
9. 템플릿 콜백 패턴 적용
클래스 구성
com
•
dao
◦
UserDao
◦
DaoFactory
◦
StatementStrategy
•
domain
◦
User
test
•
com.dao
◦
UserDaoTest
코드
UserDao
DaoFactory
StatementStrategy
UserDaoTest
개념
템플릿 콜백 패턴
토비의 스프링은 템플릿/콜백 패턴을 아래와 같이 정의한다.
전략 패턴의 기본 구조에 익명 내부 클래스를 활용하는 방식을 스프링에서는 템플릿/콜백 패턴이라고 부른다. 전략 패턴의 Context를 템플릿이라 부르고, 익명 내부 클래스로 만들어지는 오브젝트를 콜백이라고 부른다.
핵심을 다음과 같이 정리할 수 있다.
•
템플릿 콜백 패턴은 전략 패턴의 응용이다.
•
변하지 않는 부분인 템플릿에 변하는 부분을 익명 내부 클래스(콜백 방식)로 기능하게 한다.
템플릿 콜백의 작업 흐름
•
클라이언트는 콜백 오브젝트를 만들고, 템플릿 메소드를 호출할 때 콜백을 전달한다.
•
템플릿은 정해진 작업 흐름 중 콜백 오브젝트의 메소드를 호출한다. 콜백은 클라이언트 메소드의 정보와 템플릿이 제공한 참조정보를 이용해서 작업을 수행하고 그 결과를 다시 템플릿에 돌려준다.
•
템플릿은 콜백이 돌려준 정보를 사용해 작업을 마친다.
DI 방식의 전략 패턴 구조라고 생각하면 간단하다!
요약
•
UserDao
◦
기존에 AddStatement, DeleteAllStatement 클래스에 담은 내용을 add(), deleteAll() 메소드에서 익명 클래스로 담았다. 이러한 방식을 템플릿 콜백 패턴이라 부른다.
◦
AddStatement, DeleteAllStatement 클래스를 삭제하여 클래스의 개수가 늘어나지 않도록 한다.
10. 템플릿 클래스 분리
클래스 구성
com
•
dao
◦
UserDao
◦
DaoFactory
◦
StatementStrategy
◦
JdbcContext
•
domain
◦
User
test
•
com.dao
◦
UserDaoTest
코드
UserDao
DaoFactory
StatementStrategy
JdbcContext
UserDaoTest
요약
•
UserDao
◦
기존에 jdbcContextWithStatementStrategy() 메소드를 JdbcContext 클래스로 분리하였다.
◦
UserDao는 생성자가 호출될 때 JdbcContext 객체를 생성한다.
◦
JdbcContext 객체를 참조해 deleteAll() 메소드를 한 줄로 구현하였다. 코드가 굉장히 간단해졌다.
•
JdbcContext
◦
workWithStatementStrategy() 메소드는 기존의 jdbcContextWithStatementStrategy() 메소드의 내용을 담는다.
◦
executeSql(final String query)는 query를 변하지 않는 상수로 받아 workWithStatementStrategy() 메소드에 값을 넘기며 실행한다. workWithStatementStrategy()는 넘겨받은 쿼리문을 템플릿에 맞춰 수행한다.
10. 스프링의 JdbcTemplate 적용
클래스 구성
com
•
dao
◦
UserDao
◦
DaoFactory
•
domain
◦
User
test
•
com.dao
◦
UserDaoTest
코드
UserDao
DaoFactory
UserDaoTest
개념
JdbcTemplate
•
스프링이 제공하는 JDBC 코드용 템플릿이다.
•
템플릿 콜백 패턴이 적용되어있다.
•
자주 사용되는 패턴을 가진 콜백은 템플릿에 결합시켜놓아 간단한 메소드 호출만으로 전체 기능을 사용할 수 있다.
JdbcTemplate.update()
DB에서 sql을 실행한다. 다음과 같은 방식으로 활용할 수 있다.
•
update(String sql)
◦
입력받은 sql을 수행한다.
•
update(String sql, Object... args)
◦
입력받은 sql을 수행한다.
◦
sql문에 치환자가 있다면, 함께 바인딩할 파라미터를 순서대로 입력한다.
•
add(), deleteAll() 메소드는 이러한 update() 메소드를 활용하였다.
jdbcTemplate.queryForObject()
DB에서 id값으로 한 줄을 읽어 온다. 다음과 같은 방식으로 활용할 수 있다.
•
queryForObject(String sql, Class<T> requiredType)
◦
입력받은 sql을 수행하고, requiredType으로 반환한다.
•
queryForObject(String sql, RowMapper<T> rowMapper, Object... args)
◦
입력받은 sql에 치환자를 args에서 바인딩한다.
◦
Resultset에서 User 객체를 생성해 반환하기 위해 RowMapper의 구현체를 입력한다.
•
get(), getCount() 메소드는 이러한 queryForObject() 메소드를 활용하였다.
RowMapper 설명 참고
•
•
요약
•
UserDao
◦
JdbcContext 객체를 참조했던 모든 메소드들을 JdbcTemplate를 사용하도록 코드를 수정하였다.
◦
StatementStrategy도 사용하지 않고, JdbcTemplate 메소드들에 직접 쿼리문을 전달한다.
•
JdbcContext, StatementStrategy 클래스 삭제
11. getAll(), getAllTest() 추가
클래스 구성
com
•
dao
◦
UserDao
◦
DaoFactory
•
domain
◦
User
test
•
com.dao
◦
UserDaoTest
코드
UserDao
DaoFactory
UserDaoTest
개념
JdbcTemplate.query()
DB에서 sql에 따라 여러 줄을 읽어온다. 다음과 같은 방식으로 활용될 수 있다.
•
query(String sql, RowMapper<T> rowMapper)
◦
Resultset에서 User 객체를 생성해 반환하기 위해 RowMapper의 구현체를 입력한다.
•
getAll() 메소드는 query 메소드를 사용하였다.
RowMapper 설명 참고
•
•
멤버변수 활용 방안
•
멤버변수로 인터페이스와 그에 대한 구현 함수를 선언할 수 있다.
예시 코드
요약
•
UserDao
◦
기존에 get(), getAll() 함수에 각각 구현되었던 RowMapper와 구현 메소드를 멤버변수에 선언하여 사용하였다.
◦
모든 메소드들이 한 줄로 기능되도록 작성되었다.
•
UserDaoTest
◦
getAll() 함수를 테스트하는 함수를 새로 작성하였다.
◦
getAll() 함수는 List<User> 자료형을 반환하므로, 이를 받아서 size(), 객체 멤버변수 등을 비교하여 검증한다.
에러 대처 기록
위와 같은 코드를 완성하기까지 마주했던 에러와 그에 대한 대처 방안을 기록하였다.
1. @Bean과 private
스프링 IoC를 적용한 후, 테스트 함수를 실행하였는데 ApplicationContext를 load하지 못하였다며 에러가 발생했다.
자세한 에러 메시지는 아래와 같았다.
Caused by: org.springframework.beans.factory.parsing.BeanDefinitionParsingException: Configuration problem: @Bean method 'localConnectionMaker' must not be private or final; change the method's modifiers to continueOffending resource: com.dao.DaoFactory
@Bean method인 localConnectionMaker가 private이거나 final이면 안된다고 말하고 있다.
처음 함수를 작성할 때 localConnectionMaker(), awsConnectionMaker()는 클래스 외부에서 호출될 일이 없을 것이라 생각해 접근제어자를 private로 설정하였다. 그러나 여기에 @Bean을 붙이기 위해서는 접근제어자를 public으로 변경해주어야 한다. @Bean이 클래스의 외부인 ApplicationContext에서 관리하는 함수라는 표시이기 때문이다.
접근제어자를 public으로 변경하자, 오류가 해결되었다.
2. NullPointerException
DaoFactory 클래스에 DataSource를 적용하기 위해 ConnectionMaker를 사용하던 기존의 방법을 수정하였다. 그 후 Test 코드를 실행했고 다음과 같은 에러메시지를 받았다.
처음에는 deleteAll()에 빨간줄이 그어져 있어 테스트코드에서 userDao의 객체가 비어있다고 생각했다. 그러나 원인은 다른 곳에 있었다. 오류메시지가 링크로 원인을 알려주었다.
오류메시지가 가리키는 링크를 따라가 Connection c가 비어있다는 것을 알게 되었다. Connection c가 비어있던 이유는 DataSource의 코드가 잘못 작성되었기 때문이었다.
코드를 작성할 때 중복되는 코드를 복사 붙여넣기로 작성하다보니, setUrl() 메소드만 세 번을 호출하였다.
코드를 바꿔주니 정상적으로 잘 작동하였다.
