কোকিল হ্যাশিং


কাঠিন্য মাত্রা কঠিন
প্রায়শই জিজ্ঞাসা করা হয় এপিক সিস্টেম Flipkart গুগল মাইক্রোসফট Netflix এর টেসলা
কাটা হ্যাশ

সমস্যার স্ট্যাটমেন্ট

কোটিতে যখন সংঘর্ষ ঘটে তখন সমস্যা সমাধানের জন্য কোকিল হ্যাশিং একটি পদ্ধতি ব্যবহৃত হয় হ্যাশ টেবিল। সংঘর্ষগুলি সম্ভবত একটি টেবিলের একটি হ্যাশ ফাংশনের দুটি হ্যাশ মান হতে পারে। যখন একটি টেবিলের হ্যাশ ফাংশনে একই কী এর জন্য দুটি হ্যাশ মান ঘটে তখন একটি সংঘর্ষ ঘটে। এই সংঘর্ষের সমাধানের জন্য আমরা কোকিল হ্যাশিং ব্যবহার করি।

নাম অনুসারে, কোকিল হ্যাশিং একটি কোকিলের কিছু বৈশিষ্ট্য থেকে উদ্ভূত, যেমন কোকিলের ছানাটি একটি বাচ্চা বাছা বাছা করে বাসা ছাড়িয়ে অন্য ডিম বা বাচ্চাদের বাসা থেকে বের করে দেয় for আমরা কোকিল হ্যাশিং-তে একই কাজ করি, হ্যাশ টেবিলের মধ্যে একটি নতুন কী sertোকানোর চেষ্টা করছি আমরা কেবল পুরানো কীটিকে নতুন জায়গায় ঠেলাচ্ছি। এবং কোকিল হ্যাশিং এভাবেই বাস্তবায়ন করেছিলেন।

ধাক্কা

যখন একটি নতুন কী, যা আমরা একটি হ্যাশ টেবিলটি সন্নিবেশ করানোর চেষ্টা করি তখন একটি হ্যাশ টেবিলের মধ্যে ইতিমধ্যে দখল করা স্থানটি খুঁজে পায়। সেক্ষেত্রে এই পরিস্থিতিকে সংঘর্ষ বলে। যখন একটি নতুন কী inোকানোর মতো কোনও জায়গা নির্দেশ করে যা ইতিমধ্যে একটি হ্যাশ টেবিলের মধ্যে রয়েছে এটি একটি সংঘর্ষ বলে।

এই পরিস্থিতি সামান্য কিছু হ্যান্ডলিং কৌশল ব্যবহার করে পরিচালনা করা যেতে পারে।

  • সম্বোধন বা পৃথক চেইনিং বন্ধ
  • খোলা সম্বোধন

সম্বোধন বা পৃথক চেইনিং বন্ধ

পৃথক শাইনিং হ্যাশ টেবিলগুলির সংঘর্ষের সমস্যাগুলি পরিচালনা করার অন্যতম কৌশল। পৃথক চেইনিংয়ে, ধারণাটি একই হ্যাশ ফাংশন মানের জন্য রেকর্ড সংরক্ষণ করার জন্য একটি লিঙ্কযুক্ত তালিকার একটি ঘরে যোগদান করা the

খোলা সম্বোধন

সংঘর্ষের সমস্যা সমাধানের জন্য ওপেন অ্যাড্রেসিংও একটি পদ্ধতি। ওপেন অ্যাড্রেসিংয়ে, সমস্ত কী এবং মানগুলি হ্যাশ সারণীতে সংরক্ষণ করা হয়। টেবিলের আকার হ্যাশ টেবিলের উপস্থিত কীগুলির চেয়ে বড় বা সমান হওয়া উচিত এবং এটি যে কোনও সময়ে ঘটতে পারে।

কোকিল হ্যাশিং

একটি কোকিল হ্যাশিংয়ে, দুটি ধারণা রয়েছে যে বাস্তবায়নের জন্য এই পদ্ধতিটি ব্যবহার করা হয়েছিল যা হে (1) সবচেয়ে খারাপ পরিস্থিতি দেখার জন্য গ্যারান্টিযুক্ত রয়েছে।

সেগুলি ধারণাগুলি হ'ল:

একাধিক পছন্দ: আমরা কী-এর জন্য F1 (কী) এবং F2 (কী) beোকানোর জন্য কোনও পছন্দকে অনুমতি দিতে মুক্ত।

স্থানান্তর: এফসি (কী) এবং এফ 1 (কী) উভয়ই দখল করলে একটি ক্ষেত্রেও সম্ভব হয়। সুতরাং, এটি কোকিল পাখির বৈশিষ্ট্যটিকে এমনভাবে অনুলিপি করার চেষ্টা করবে যাতে অন্যান্য ডিম বা ছোটদের বাসা থেকে বের করে দেয়। হ্যাশ টেবিলের মধ্যে একটি নতুন কী ঠেলে দেওয়ার প্রয়াসে। তারপরে, এটি পুরানো কীটি কোনও নতুন জায়গায় ঠেলাতে পারে। সেই পুরানো চাবিটির জন্য জায়গা খুঁজে পেতে এখন আমাদের সমস্যা।

এখন দুটি জিনিস আছে। যদি সেই পুরানো কীটির জন্য কোনও নতুন জায়গা খালি স্থান হয় তবে এটি ভাল। তবে এটি যদি শূন্য স্থান না হয় তবে… ??

যদি এই শর্তটি দেখা দেয় তবে আমাদের সেই নতুন কীটি পাশাপাশি স্থানান্তর করতে হবে এবং এর জন্য একটি নতুন জায়গা খুঁজে পেতে হবে। এখন যদি আবার সেই পরিস্থিতি দেখা দেয়, তবে আমরা কীটির জন্য খালি শূন্যস্থান খুঁজে না পাওয়া পর্যন্ত বার বার কেবল নতুন জায়গায় কীটি স্থানান্তর করতে হবে।

 

কোকিল হ্যাশিং - সবচেয়ে খারাপ কেস ও (1)

মূলত, এখানে 3 টি অপারেশন রয়েছে যা একটি হ্যাশ টেবিল দ্বারা সমর্থিত (বা ভাষাগুলিতে কোনও উপযুক্ত পদ্ধতি):

  • লুকআপ (কী): একটি বুলিয়ান ফাংশন, উপস্থিত বা না থাকলে সত্য / মিথ্যা ফেরত দেয়।
  • সন্নিবেশ (কী): একটি নতুন জায়গা তৈরি করুন এবং নতুন এন্ট্রি হলে সেই আইটেমটি "কী" টি হ্যাশ টেবিলটিতে সন্নিবেশ করুন।
  • মুছে ফেলুন (কী): হ্যাশ টেবিল থেকে "কী" মুছুন।

 

কোকিল হ্যাশিং কোকিল হ্যাশিং কোকিল হ্যাশিং কোকিল হ্যাশিং কোকিল হ্যাশিং কোকিল হ্যাশিং কোকিল হ্যাশিং

 

কোড

সি ++ কোকিল হ্যাশিং বাস্তবায়ন করতে

#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

জটিলতা বিশ্লেষণ

সময় জটিলতা

সন্নিবেশ: ও (1)

মোছা: ও (1)

স্পেস জটিলতা ity

ও (1) কোন অতিরিক্ত স্থান প্রয়োজন হিসাবে।