데이터 구조 : 초기화, 삽입, 결실, 요소를 발견하는 모든 요소를

이 0에서 N 원소를 보유하는 데이터 구조를 제안을 - 1을 지원하고, 요소의 검색, 요소의 삭제, 모든 요소 삭제, 요소의 삭제, 요소의 삽입, O (1) 시간에서 다음 작업을 모두 지원합니다.

해시 테이블 (충돌이없는 것으로 가정)이 O (1)에서 삽입 및 검색을 지원합니다. 그래도 삭제에 대해서는 확실하지 않습니다 ... 어떤 아이디어?

2011-10-02 user7

OK가 나는 N 분노 내에 있는지 방금

0)Initialize 
memset(A,0,sizeof(A)) 

1) Insert i 
A[i] = 1 

2) Remove i 
A[i] = 0 

3) Find i 
if(A[i]) 

4) Delete All 
memset(A,0,sizeof(A))

2011-10-02 17:17:40 FUD

bool allDelete = true? – user7

답장을 보내 주셔서 감사합니다 ... 그것은 의미가 있지만 .. memset O (1) 작업입니까? – user7

memset()이 O (1) 연산이 아니라고 가정해야한다고 생각합니다. –

해시 테이블 될 O (1)에 대한 삭제 N 요소의 어레이를 선언 할 수있다라고 생각한다.

List<Object> hashTableData = new ArrayList<Object>();

편집 : 코드는 해시 테이블에 대해 저장된 데이터의 가능한 구현입니다.

2011-10-02 17:18:43 DwB

나는 자바 프로그래머가 아니기 때문에 일반적으로 해시 테이블은 일반적으로 연결된 목록에 대한 포인터의 배열이며 실제로 해시 테이블에서 모든 요소를 삭제하기 위해 처음에는 해방해야한다. 각 연결 목록 ... O (n) 작업이 아닙니다. – user7

"충돌이 없다고 가정합니다"를 포함 시켰습니다. 그것은 그것이 어떻게 구현되는지에 달려있다. 배열을 가지고 해시 함수를 사용하여 원하는 항목의 인덱스를 얻고 해시 함수가 중복을 만들지 않으면 연결된 목록, 배열 만 필요하지 않습니다. – DwB

나는 네가 옳은 것 같아. 해시 함수가 충분히 "임의"인 경우 삽입, 제거 및 조회에 O (1) 시간이 필요합니다. 그러나 충돌이 없더라도 모든 요소 O (1)을 초기화하고 삭제합니까? – user7

매우 흥미로운 질문입니다!

메모리 할당 및 해제가 O (1)라고 가정하면 모든 사용자가 O (1)를 사용할 수 있습니다.

이것을 위해 우리는 Hopcroft와 Ullman의 트릭을 사용합니다.이 기법을 사용하면 실제로 크기를 초기화하는 데 오메가 (n) 시간을 들이지 않고도 크기 n의 배열을 사용할 수 있습니다.

여기를 참조하십시오 : 우리는 배열 요소가 초기화되지 않는 것을 발견하면 http://eli.thegreenplace.net/2008/08/23/initializing-an-array-in-constant-time/

가 삽입에, 우리는 단지 검색에 1. 위의 배열을 사용하고 설정, 우리는, 삭제에 0을 반환

모두 삭제에서는 데이터 구조를 해제하고 새 구조체를 사용합니다.

2011-10-03 06:07:49

검색 값이 존재하는 인덱스를 모르는 경우 검색 작업은 O (1)가됩니다. –

@cyber_raj : 배열은 초기화되지 않은 요소에 액세스하는 경우 O (1) 시간에서 알 수있는 것을 제외하고는 다른 배열과 같습니다.이 경우 기본 초기화 값을 반환 할 수 있습니다. 위의 블로그 링크의 "솔루션"섹션에서 1 번을 읽으십시오. –

처음부터 []와 []의 초기화가 초기화되지 않은 경우 vec [i]가 설정되었다는 것을 주장하는 데 필요한 요구 사항을 충족하는 가비지 데이터가 들어 있습니까? 드문 경우지만 기술적으로 가능하지 않습니까? –

데이터 구조 : 초기화, 삽입, 결실, 요소를 발견하는 모든 요소를 ​​