본문 바로가기

CS공부/자료구조6

[Java] 해시함수의 충돌을 피하기 위해 테이블 사이즈를 소수, 홀수로 만들어야 하는 이유 해시함수의 충돌을 피하기 위해서는 테이블 크기를 홀수로 만들거나, 소수로 설정하거나, 크기 자체를 늘리는 것이 좋다고 한다. 그런데 강의 해주시는 교수님은 왜 충돌이 발생하는지 설명만 하고 왜 테이블 크기를 늘려야 하는건지는 설명해주지 않으셨다. 그래서 쓰는 글. 해시함수는 key값에서 정수값을 계산하는데 이 때 해시 테이블의 길이를 벗어나지 않기 위해서 테이블 길이로 해시함수의 리턴값을 모듈러(%-나머지값) 연산한다고 한다. 예를 들어 테이블의 크기가 6이고 특정 해시 함수를 사용했을 때 2의 배수를 반환한다면 2, 4, 6, 8, 10 … 가 해시함수에서 반환되는데 이를 해시 테이블 사이즈에 맞게 조정(모듈러 사용)하면 2(2%6), 4(4%6), 0(6%6), 2(8%6), 4(10%4) … 로 변.. 2022. 12. 8.
[Java] Iterator과 Iterable 그리고 iterator()을 알아보자(alaboza..) 네이버 부스트코스의 자료구조를 수강하다 연결리스트의 반복자 선언 부분에 이르렀는데 또 막히는 부분이 생겼다 바로 iterator.. Public Iterator iterator() { return new IteratorHelper(); } 라는 코드를 써놓고 IteratorHelper()에 해당하는 부분을 LinkedList 안에 만들어줘야 한단다. public class LinkedList implements ListI { class IteratorHelper implements Iterator { ...구현 } } 이렇게! 대충 해줘야 한다니까 음음 그렇군 하고 봤는데 코드를 다시 보니 이게 뭐지? 싶었다. 교수님은 Iterator iterator() 파트를 Iterator인터페이스를 iterator.. 2022. 12. 2.
[Java] 연결리스트의 remove 메소드에서 오버라이드 없이 compareTo를 사용한다? 네이버 부스트코스로 자료구조를 듣던 와중 신기한 코드를 발견했다. if(((Comparable) current.data).compareTo(obj) == 0) 라는 코드인데 설명만 보면 current.data를 Comparable로 캐스팅해서 compareTo메소드를 사용해주는 것이라고 한다. 그런데 여기서 드는 의문 compareTo 메소드를... 오버라이드 하지 않고 사용할 수 있었던가????? 그리고 애시당초 인터페이스로 캐스팅된다는 말이 무슨 말이지??????.... 라는 많은 고민 끝에 작성하게 된 글 (검색을 많이 해봤지만 기본적인건지 명확한 답을 구하긴 어려웠다...ㅎㅎ) 우선 인터페이스로 캐스팅 시키는건 흔한 일은 아니다. 보통 extends로 만든 자식 클래스를 부모 클래스로 만들어줄 때.. 2022. 12. 2.
[Java] 연결 리스트를 공부하고 있는데 포인터라는 말이 계속 나온다 자료구조 공부 중 연결 리스트에서 addLast 메소드 부분을 보고 있는데 진짜 이해 안가는 부분이 있었다. public void addLast(E obj) { Node newNode = new Node(obj); Node tmp = head; while(tmp.next != null) { tmp = tmp.next; } tmp.next = newNode; } 라는 코드에서 tmp.next = newNode를 하면 tmp뿐만 아니라 tmp라는 변수에 저장된 노드에도 newNode가 저장된단다. 강의 듣는 와중에는 응응... 글쿤하고 지나갔는데 코드를 보면 볼수록 이해가 안가기 시작했다. 아니 진짜 말이 안되는게 변수 i에 변수a를 저장하고(i=a) i에 5를 저장했다고(i=5) 했다고 a가 5가 됐다는 .. 2022. 12. 1.
반응형

티스토리툴바