CS/자료구조2 해시 충돌(Hash Collision)과 최적화 방법 해시 충돌 해시함수는 해시테이블의 키 값으로 레코드가 저장되어 있는 주소(또는 색인)을 산출하는 함수이다. 다른 내용의 데이터가 같은 키를 갖는 상황을 해시 충돌이라고 하는데, 같은 키 값이 생긴다는 것은 특정 키의 버켓에 데이터가 집중된다는 뜻이다. 따라서 빈번한 해시 충돌은 해시테이블의 성능을 저하시킨다. 해결 방법 1) 체이닝 버켓 내에 연결리스트를 할당하여, 버켓에 데이터를 삽입하다가 해시 충돌이 발생하면 연결리스트로 데이터를 연결하는 방식이다. 복잡한 계산식을 사용할 필요가 없고, 삭제 또는 삽입이 용이하다. 해결 방법 2) 개방 주소법 체이닝의 경우 버켓이 꽉 차더라도 연결리스트로 계속 늘려갈 수 있기 때문에 데이터의 주소값은 바뀌지 않는다. 그러나 개방 주소법은 해시 충돌이 일어나면 다른 버.. 2021. 11. 22. Stack vs Queue Stack 개요 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 LIFO(Last In First Out) 구조 순차적으로 데이터를 추가하고 삭제하는 스택에는 ArrayList와 같은 배열 기반의 컬렉션 클래스가 적합 ex. 수식계산, 수식괄호검사, undo/redo, 웹 브라우저의 뒤로/앞으로 구현 import java.util.*; class MyStack extends Vector { public Object push(Object item){ addElement(item); return item; } public Object pop(){ Object obj = peek(); //만일 Stack이 비었다면 peek 메서드가 예외 발생 removeElementAt(size() - 1); //마지막 요소.. 2021. 9. 24. 이전 1 다음
