뻐꾸기 시퀀스 프로그램

난이도 하드
자주 묻는 질문 에픽 시스템 Flipkart 구글 Microsoft 넷플릭스 테슬라
해시 해싱조회수 55

문제 통계

Cuckoo 시퀀스 프로그램 또는 Cuckoo Hashing은 충돌이 발생할 때 문제를 해결하기 위해 사용되는 방법입니다. 해시 테이블. 충돌은 테이블에있는 해시 함수의 두 해시 값일 가능성이 있습니다. 테이블의 해시 함수에서 동일한 키에 대한 두 개의 해시 값이 발생하면 충돌이 발생합니다. 이 충돌을 해결하기 위해 우리는 Cuckoo Hashing을 사용합니다.

이름에서 알 수 있듯이 Cuckoo Hashing은 뻐꾸기의 병아리가 다른 알이나 어린 알을 둥지에서 밀거나 밀어서 자신의 장소를 만들기 위해 뻐꾸기의 일부 특성에서 파생되었습니다. Cuckoo Hashing에서하는 것과 동일하게 해시 테이블에 새 키를 삽입하려고하면 이전 키를 새 위치로 푸시합니다. 이것이 Cuckoo Hashing이 구현 된 방식입니다.

충돌

해시 테이블에 삽입하려는 새 키가 해시 테이블에서 이미 점유 된 위치를 찾을 때. 이 경우 이러한 상황을 충돌이라고합니다. 새 키가 이미 해시 테이블에 점유 된 삽입 위치를 나타내는 경우 충돌이라고합니다.

이 상황은 충돌 처리 기술 중 일부를 사용하여 처리 할 수 ​​있습니다.

  • 폐쇄 된 주소 지정 또는 별도의 체인
  • 주소 지정 열기

폐쇄 된 주소 지정 또는 별도의 체인

Separed Chaining은 Hash의 충돌 문제를 처리하는 기술 중 하나입니다. 테이블. 분리 체이닝에서 개념은 셀을 연결 목록에 결합하여 동일한 해시 함수 값에 대한 레코드를 저장하는 것입니다.

주소 지정 열기

Open Addressing은 충돌 문제를 해결하는 방법이기도합니다. 개방 주소 지정에서 모든 키와 값은 해시 테이블에 저장됩니다. 테이블의 크기는 해시 테이블에있는 키보다 크거나 같아야하며 언제든지 발생할 수 있습니다.

뻐꾸기 해싱

Cuckoo Hashing에는 최악의 경우 O (1) 조회 시간을 보장하는 구현을 달성하기 위해이 메서드가 사용하는 두 가지 개념이 있습니다.

이러한 개념은 다음과 같습니다.

다중 선택 : F1 (키) 및 F2 (키)를 삽입 할 키를 자유롭게 선택할 수 있습니다.

재배치 : F1 (키) 및 F2 (키)가 모두 사용되는 경우도 가능합니다. 따라서 다른 알이나 어린 알을 둥지 밖으로 밀어내는 방식으로 뻐꾸기 새의 특성을 모방하려고합니다. 해시 테이블에 새 키를 밀어 넣으려고합니다. 그런 다음 이전 키를 새 위치로 밀 수 있습니다. 이제 우리는 이전 키의 위치를 ​​찾는 데 문제가 있습니다.

이제 두 가지가 있습니다. 이전 키의 새 위치가 빈 공간이면 좋습니다. 하지만 비어 있지 않으면… ??

이 조건이 발생하면 새 키도 교체하고 새 위치를 찾아야합니다. 이제 다시 이러한 조건이 발생하면 키를위한 빈 공간이 비어있는 것을 찾을 때까지 키를 반복적으로 새 위치로 옮겨야합니다.

 

Cuckoo Hashing – 최악의 경우 O (1)

기본적으로 해시 테이블 (또는 언어의 적절한 방법)에서 지원하는 세 가지 작업이 있습니다.

  • Lookup (key) : Boolean 함수, 존재 여부에 관계없이 True / False를 반환합니다.
  • Insert (key) : 새 자리를 만들고 새 항목이있는 경우 해당 항목 "Key"를 Hash Table에 삽입합니다.
  • 삭제 (키) : 해시 테이블에서“키”를 삭제합니다.

 

뻐꾸기 해싱 뻐꾸기 해싱 뻐꾸기 해싱 뻐꾸기 해싱 뻐꾸기 해싱 뻐꾸기 해싱 뻐꾸기 해싱

 

암호

Cuckoo Hashing 구현을위한 C ++

#include<bits/stdc++.h>
#define TNO 2
#define MOD 6

using namespace std;

int cuckooTable[TNO][MOD];
int POSITION[TNO];

void fillTable()
{
    for (int j=0; j<MOD; j++)
        for (int i=0; i<TNO; i++)
            cuckooTable[i][j] = INT_MIN;
}

void printTable()
{
    cout<<"Hash Tables are:\n"<<endl;
    for (int i=0; i<TNO; i++, printf("\n"))
    {
        int k=i+1;
        cout<<"Table: "<<k<<"-> ";
        for (int j=0; j<MOD; j++)
        {
            if(cuckooTable[i][j]==INT_MIN)
                cout<<" N ";
            else
                cout<<" "<<cuckooTable[i][j];
        }
    }
    cout<<endl;
}

int getHashValue(int function, int key)
{
    switch (function)
    {
    case 1:
        return key%MOD;
    case 2:
        return (key/MOD)%MOD;
    }
}
void getArrange(int key, int id, int c, int n)
{
    if (c==n)
    {
        cout<<key<< " do not have a position\n"<<endl;
        //cycle present rehash
        return;
    }
    for (int i=0; i<TNO; i++)
    {
        POSITION[i] = getHashValue(i+1, key);
        if (cuckooTable[i][POSITION[i]] == key)
            return;
    }
    if (cuckooTable[id][POSITION[id]]!=INT_MIN)
    {
        int dis = cuckooTable[id][POSITION[id]];
        cuckooTable[id][POSITION[id]] = key;
        getArrange(dis, (id+1)%TNO, c+1, n);
    }
    else
        cuckooTable[id][POSITION[id]] = key;
}

void cuckooFunction(int keys[], int n)
{
    fillTable();
    for (int i=0, c=0; i<n; i++, c=0)
        getArrange(keys[i], 0, c, n);

    printTable();
}
int main()
{
    int keyTable1[] = {77, 53, 44, 37, 24, 55};

    int n = sizeof(keyTable1)/sizeof(int);

    cuckooFunction(keyTable1, n);

    int keyTable2[] = {77, 53, 44, 37, 24, 55};

    int m = sizeof(keyTable2)/sizeof(int);

    cuckooFunction(keyTable2, m);

    return 0;
}
Hash Tables are:

Table: 1->  24 55 44 N  N  77
Table: 2->  37 N  53 N  N  N

Hash Tables are:

Table: 1->  24 55 44 N  N  77
Table: 2->  37 N  53 N  N  N

자바의 뻐꾸기 시퀀스 프로그램

import java.util.*;

class CuckooHashing
{
    private static int MOD = 6;
    private static int TNO = 2;
    private static int [][]cuckooTable = new int[TNO][MOD];
    private static int []POSITION = new int[TNO];

    public static void fillTable()
    {
        for (int j = 0; j < MOD; j++)
            for (int i = 0; i < TNO; i++)
                cuckooTable[i][j] = Integer.MIN_VALUE;
    }
    
    public static int getHashValue(int function, int key)
    {
        switch (function)
        {
        case 1:
            return key % MOD;
        case 2:
            return (key / MOD) % MOD;
        }
        return Integer.MIN_VALUE;
    }
    
    public static void getArrange(int key, int id, int c, int n)
    {
        if (c == n)
        {
            System.out.println(key+" is not  have a position");
            return;
        }
        for (int i = 0; i < TNO; i++)
        {
            POSITION[i] = getHashValue(i + 1, key);
            if (cuckooTable[i][POSITION[i]] == key)
                return;
        }
        if (cuckooTable[id][POSITION[id]] != Integer.MIN_VALUE)
        {
            int dis = cuckooTable[id][POSITION[id]];
            cuckooTable[id][POSITION[id]] = key;
            getArrange(dis, (id + 1) % TNO, c + 1, n);
        }
        else
            cuckooTable[id][POSITION[id]] = key;
    }
    
    public static void printTable()
    {
        System.out.println("Hash Tables are:");

        for (int i = 0; i < TNO; i++, System.out.println())
        {
            int t=i+1;
            System.out.print(" Table: " + t+" --> " );
            for (int j = 0; j < MOD; j++)
            {
                if(cuckooTable[i][j] == Integer.MIN_VALUE)
                    System.out.print(" N ");
                else
                    System.out.print(" "+ cuckooTable[i][j]);
            }
            System.out.println();
        }
    }
    
    public static void cuckooFunction(int keys[], int n)
    {
        fillTable();

        for (int i = 0, cnt = 0; i < n; i++, cnt = 0)
            getArrange(keys[i], 0, cnt, n);

        printTable();
    }
    
    public static void main(String[] args)
    {
        int KeysTable1[] = {77, 53, 44, 37, 24, 55};

        int n = KeysTable1.length;

        cuckooFunction(KeysTable1, n);
        int KeysTable2[] = {77, 53, 44, 37, 24, 55};

        int m = KeysTable2.length;

        cuckooFunction(KeysTable2, m);
    }
}
Hash Tables are:
 Table: 1 -->  24 55 44 N  N  77

 Table: 2 -->  37 N  53 N  N  N

Hash Tables are:
 Table: 1 -->  24 55 44 N  N  77

 Table: 2 -->  37 N  53 N  N  N

복잡성 분석

시간 복잡성

삽입 : O (1)

삭제 : O (1)

공간 복잡성

O (1) 추가 공간이 필요하지 않습니다.

Translate »
1