CS(Computer Science)/자료구조 (총 11개) 썸네일형 리스트형 자료구조 - 해시 함수(Hash Collision)종류와 충돌 처리 방식 해시 충돌(Hash Collision)이란- 서로 다른 키를 가진 레코드들이 하나의 버킷에 매핑되는 경우- 아래 그림을 보면 John Smith 와 Sandra dee를 해시함수 하여 동일한 해시값(02) 가 출력된 것을 볼 수 있는데 이가 해시 충돌이다. 문제점- 해시 함수의 충돌은 해싱의 검출 속도를 떨어뜨리는 결과를 초래한다- 버킷 오버플로우가 발생한다 해시 함수- 해시함수는 해시테이블의 공간 전체에 고르게 저장할 수 있어야 한다(최대한 충돌을 발생하지 않게 해야한다.)- 충돌이 많이 발생할 수록 저장하는 시간과 검출 시간이 오래걸린다.- 계산이 간단해야한다. 1. Division - 저장하려는 데이터를 해시 테이블의 크기로 나눈 나머지의 값을 해시값(저장될 주소)으로 하여 저장 2. 제곱함수 - .. 자료구조 - 단일 연결리스트(Linked List) 단일연결리스트 - 모든 원소가 데이터, 링크 쌍으로 이루어져있고 이 링크를 통해 자신의 후속 원소와 연결되는 구조를 말한다.- 앞서말했듯이 연결구조는 원소의 삽입과 삭제가 용이하다(미리 지정된 연속된 주소공간으로 리스트가 표현되는 것이 아닌 각각의 원소가 다음 원소의 주소를 가지고 있기 때문에 삽입시에 공간을 늘리지 않아도 되기 때문이다.) 1. 삽입a) 제잎 앞에 원소 삽입1. 새로운 노드의 링크를 헤더의 다음 노드를 가리키도록 한다.2. Header의 링크를 새로운 노드를 가리키게 한다.*1 , 2번의 순서가 뒤바뀌면 Header의 다음노드를 가리키는 링크가 사라지기 때문에 1, 2번의 순서를 꼭 지켜야한다. 다음그림은 연결구조에서 맨앞에 원소의 삽입을 나타낸 그림이다*코드 12345678910111.. 자료구조 - 순차표현 연결표현 *순차표현 - 메모리에 연속적인 공간을 할당받은 데이터이다. - 배열이 이에 해당된다 장점- 연속된 메모리로 표현되기 때문에 원소의 위치를 나타내는 인덱스가 곧바로 주소로 변경가능하므로 접근이 빠르다. 단점- 연속적인 공간을 할당 받기위해 처음에 크기가 정해지기 때문에 원소의 추가시 시간이 오래걸린다 (크기를 다시잡고 원래의 데이터를 옮기는 과정이 필요하기 때문이다.)- 원소의 삽입과 삭제가 어렵다 배열의 중간에 원소의 삽입과 삭제가 일어나면 필요한 만큼 뒤로 밀거나 당겨와야한다. 위의 그림은 int형 자료의 배열을 나타내는 그림이다. int형의 크기는 4byte이므로 메모리상에서 각각의 원소의 거리가 4만큼씩 떨어져 있는 것을 볼 수 있다. *연결표현 - 원소들이 저장된 메모리의 주소를 상관하지 않고 .. 이전 1 2 다음
