1

Тема: Подвійне хешування

Привіт!
Мені поставили завдання реалізувати хеш-таблицю з використанням подвійного хешування. Моя програма працює, і, здається, без помилок. Але єдине - додавання нових елементів (особливо у великій кількості - потрібно 100 000) виконується дуже повільно.
Чи не могли б ви допомогти розібратися, як краще оптимізувати цю функцію (void DoubleHashing<E, X>::add(const E e[], size_t len))?

Дякую.

Ось код:

DoubleHashing.h - файл з реалізацією

#ifndef DOUBLEHASHING_H
#define DOUBLEHASHING_H
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include "Container.h"
using namespace std;
class EmptyExc : public ContainerException
{
public:
    virtual const char* what() const throw()
    {
        return "empty";
    }
};
class PrimExc : public ContainerException
{
public:
    virtual const char* what() const throw()
    {
        return "max_prim";
    }
};
template <typename E, size_t X = 7>
class DoubleHashing : public Container<E>
{
    size_t nmax;
    size_t n;
    double maxbelfak;
    class HashElement
    {
    public:
        size_t status;
        E data;
        size_t hash;
        HashElement() //: data()
        {
            status = 0; hash = 0;
        }
        ~HashElement()
        {
        }
        void fill(const E e, unsigned int h)
        {
            hash = h; status = 1; data = e;
        }
    };
    HashElement * value;
public:
    DoubleHashing<E, X>()
    {
        value = new HashElement[X]; n = 0; nmax = X;
        maxbelfak = 0.7;
        
    }
    virtual ~DoubleHashing<E, X>()
    {
        delete[] value;
    }
    using Container<E>::add;
    virtual void add(const E e[], size_t len);
    void rehash(const E e[], size_t len);
    using Container<E>::remove;
    virtual void remove(const E e[], size_t s);
    virtual bool member(const E& e) const;
    void ocbigger(size_t n, size_t nmax);
    
    virtual size_t size() const
    {
        return n;
    }
    void Quicksort(E *a, size_t m) const
    {
        if (m < 2)
            return;
        E p = a[m / 2];
        E *l = a;
        E *r = a + m - 1;
        while (r >= l) {
            if (p > *l)
            {
                l++;
                continue;
            }
            if (*r > p)
            {
                r--;
                continue; // we need to check the condition (l <= r) every time we change the value of l or r
            }
            E t = *l;
            *l++ = *r;
            *r-- = t;
        }
        Quicksort(a, r - a + 1);
        Quicksort(l, a + m - l);
    }
    virtual size_t apply(const Functor<E>& f, Order order) const
    {
        size_t x = 0;
        size_t z = 0;
        E *copyvalue;
        if (n > 0)
        {
            if (order == dontcare)
            {
                for (z = 0; z < nmax; z++)
                {
                    if (value[z].status == 1)
                    {
                        x++;
                        if (!f(value[z].data))
                        {
                            break;
                        }
                    }
                }
            }
            else
            {
                copyvalue = new E[n];
                for (z = 0; z < nmax; z++)
                {
                    if (value[z].status == 1)
                    {
                        copyvalue[x] = value[z].data;
                        x++;
                    }
                }
                x = 0;
                Quicksort(&copyvalue[0], n);
                if (order == ascending)
                {
                    for (size_t i = 0; i < n; i++)
                    {
                        x++;

                        if (!f(copyvalue[i]))
                        {
                            break;
                        }
                    }
                }
                if (order == descending)
                {
                    for (size_t i = n; i > 0; i--)
                    {
                        x++;

                        if (!f(copyvalue[i - 1]))
                        {
                            break;
                        }
                    }
                }
                delete[] copyvalue;
            }
        }
        return x;
    }
    virtual E min() const
    {
        if (this->empty()) throw EmptyExc();
        else
        {
            E rc;
            size_t j = 0;
            for (j = 0; j < nmax; ++j)
            {
                if (value[j].status == 1)
                {
                    rc = value[j].data;
                    break;
                }
            }
            for (size_t i = j; i<nmax; i++)
            {
                if (value[i].status == 1 && rc > value[i].data)
                {
                    rc = value[i].data;
                }
            }
            return rc;
        }
    }
    virtual E max() const
    {
        if (this->empty()) throw EmptyExc();
        else
        {
            E rc;
            size_t j = 0;
            for (j = 0; j < nmax; ++j)
            {
                if (value[j].status == 1)
                {
                    rc = value[j].data;
                    break;
                }
            }
            for (size_t i = j; i<nmax; i++)
            {
                if (value[i].status == 1 && value[i].data > rc)
                {
                    rc = value[i].data;
                }
            }
            return rc;
        }
    }
    virtual ostream& print(ostream& o) const;
};
size_t prime(size_t number)
{
    size_t a = 2;
    while (a < number)
    {
        if (number % a == 0)
        {
            return 0;
        }
        a++;
    }
    return 1;
}
size_t nextprime(size_t number)
{
    size_t a = number + 1;
    while (1)
    {
        if (a < ((size_t)-1))
        {
            if (!(prime(a) == 1))
            {
                a++;
            }
            else
            {
                break;
            }
        }
        else
        {
            throw PrimExc();
        }
    }
    return a;
}
template <typename E, size_t X>
void DoubleHashing<E, X>::add(const E e[], size_t len) // ось ця функція працює повільно
{
    size_t hash1, hash2, hashg = 0;
    size_t newnmax = nmax;
    HashElement *a;
    size_t q = 0;
    if ((n + len) > (newnmax * maxbelfak))
    {
        HashElement * newvalue;

        do
        {
            newnmax = nextprime(newnmax);
        } while (newnmax < ((n + len) * 10));

        newvalue = new HashElement[newnmax];
        for (size_t i = 0; i < nmax; ++i)
        {
            if (value[i].status == 1)
            {
                hash1 = (value[i].hash) % newnmax;
                hash2 = 1 + ((value[i].hash) % (newnmax - 2));
                while (1)
                {
                    hashg = (hash1 + (q*hash2)) % newnmax;
                    if (newvalue[hashg].status == 0)
                    {
                        newvalue[hashg].fill(value[i].data, value[i].hash);
                        q = 0;
                        break;
                    }
                    else
                    {
                        q++;
                    }
                }
            }
        }
        delete[] value;
        value = new HashElement[newnmax];
        for (size_t t = 0; t < newnmax; t++)
        {
            value[t] = newvalue[t];
        }
        delete[] newvalue;
        nmax = newnmax;
    }
    for (size_t i = 0; i < len; ++i)
    {
        q = 0;
        if (!member(e[i]))
        {
            hash1 = hashValue(e[i]) % nmax;
            hash2 = 1 + (hashValue(e[i]) % (nmax - 2));
            while (1)
            {
                hashg = (hash1 + (q*hash2)) % nmax;
                a = &value[hashg];
                if (a->status == 0)
                {
                    value[hashg].fill(e[i], hashValue(e[i]));
                    n++;
                    break;
                }
                else
                {
                    q++;
                }
            }
        }
    }
}
template <typename E, size_t X>
void DoubleHashing<E, X>::remove(const E e[], size_t s)
{
    size_t hash1;
    size_t hash2;
    size_t hashg;
    size_t q = 0;
    for (size_t i = 0; i < s; ++i)
    {
        q = 0;
        hash1 = hashValue(e[i]) % nmax;
        hash2 = 1 + (hashValue(e[i]) % (nmax - 2));
        for (size_t w = 0; w < nmax; w++)
        {
            hashg = (hash1 + (q*hash2)) % nmax;
            if ((value[hashg].status == 1) && (value[hashg].data == e[i]))
            {
                value[hashg].status = 0;
                n--;
                break;
            }
            else
            {
                q++;
            }
        }
    }
}
template <typename E, size_t X>
bool DoubleHashing<E, X>::member(const E& e) const
{
    size_t hashg;
    size_t hash1;
    size_t hash2;
    size_t q = 0;
    size_t x = 0;
    hash1 = hashValue(e) % nmax;
    hash2 = 1 + (hashValue(e) % (nmax - 2));
    for (size_t j = 0; j < nmax; ++j)
    {
        hashg = (hash1 + (q*hash2)) % nmax;
        x++;
        if (value[hashg].status == 1 && value[hashg].data == e)
        {
            return true;
        }
        else
        {
            q++;
        }
    }
    return false;
}
template <typename E, size_t X>
ostream& DoubleHashing<E, X>::print(ostream& o) const
{
    HashElement *p;
    o << "Double Hashing [ n=" << n << " nmax=" << nmax << " value=";
    for (size_t i = 0; i < nmax; ++i)
    {
        if (value[i].status == 1)
        {
            p = &value[i];
            o << ' ' << p->data;
        }
        else
        {
            o << " .";
        }
    }
    o << " ]";
    return o;
}
#endif //DOUBLEHASHING_H

Container.h - допоміжний файл (має залишатися незмінним)

#ifndef CONTAINER_H
 #define CONTAINER_H
 #include <iostream>
 
enum Order
{
    dontcare, ascending, descending
};

 template <typename E> class Functor;
 
 class ContainerException : public std::exception
 {
 public:
     virtual const char* what() const throw() = 0;
 };
 
 template <typename E>
 class Container
 {
     Container& operator=(const Container<E>&);
     Container(const Container<E>&);
 public:
     Container()
     {
     }
     virtual ~Container()
     {
     }

     virtual void add(const E& e)
     {
         add(&e, 1);
     }
     virtual void add(const E e[], size_t s) = 0;

     virtual void remove(const E& e)
     {
         remove(&e, 1);
     }
     virtual void remove(const E e[], size_t s) = 0;

     virtual bool member(const E& e) const = 0;
     virtual size_t size() const = 0;
     virtual bool empty() const
     {
         return size() == 0;
     }

     virtual size_t apply(const Functor<E>& f, Order order = dontcare) const = 0;

     virtual E min() const = 0;
     virtual E max() const = 0;

     virtual std::ostream& print(std::ostream& o) const = 0;
 };
 
 template <typename E>
 inline std::ostream& operator<<(std::ostream& o, const Container<E>& c)
 {
     return c.print(o);
 }
  
 template <typename E>
 class Functor
 {
 public:
     virtual bool operator( )(const E& e) const = 0;
     virtual ~Functor()
     {
     }
 };
 
 template <typename E> inline unsigned long hashValue(const E& e)
 {
     return (unsigned long)e;
 } //e * 47114711UL
 template <typename E> inline double doubleValue(const E& e)
 {
     return double(e);
 }
 template <typename E> inline unsigned long ordinalValue(const E& e)
 {
     return (unsigned long)e;
 }
 
 #endif //CONTAINER_H

simpletest.cpp - виконуючий файл (також має залишатися незмінним)

#include <iostream>
 #include <sstream>
 #include <fstream>
 #include <string>
 #include <cstring>
 #include <cstdlib>
 #include <cctype>
 #include "DoubleHashing.h"
 
 #ifndef ETYPE
 #define ETYPE int
 #endif 
 //#define str(x) #x
 
 const char helpstr[] = 
   "new ............................... create new Container\n"
   "delete ............................ delete Container\n"
   "add <key> [...] ................... add <key>(s) with Container::add( int )\n"
   "remove <key> [...] ................ remove <key>(s) with Container::remove( int )\n"
   "member <key> ...................... call Container::member( <key> )\n"
   "size .............................. call Container::size()\n"
   "empty ............................. call Container::empty()\n"
   "min ............................... call Container::min()\n"
   "max ............................... call Container::max()\n"
   "print ............................. print container with operator<<()\n"
   "apply [asc|desc|dontcare [<n>]] ... traverse container with PrintN functor\n"
   "trace ............................. toggle tracing on/off\n"
   "fadd <filename> ................... add values read from file <filename>\n"
   "fremove <filename> ................ remove values read from file <filename>\n"
   "radd [<n> [<seed>]] ............... add <n> random values, optionally reset generator to <seed>\n"
   "rremove [<n> [<seed>]] ............ remove <n> random values, optionally reset generator to <seed>\n"
   "quit .............................. quit program\n\n"
   "arguments surrounded by [] are optional\n";

template <typename E>
class PrintN : public Functor<E>
{
    std::ostream& o;
    mutable int n;
public:
    explicit PrintN(int n = 0, std::ostream& o = std::cout) : o(o), n(n)
    {
    }
    explicit PrintN(std::ostream& o) : o(o), n(0)
    {
    }
    bool operator()(const E& e) const
    {
        o << e << ' ';
        return n <= 0 || --n;
    }
};

void setrandom(int seed)
{
    srand(seed);
}
template <typename E> E nextrandom()
{
    return E(rand());
}
 
 // Template-Spezialisierungen fuer Klasse std::string
 
template <> inline double doubleValue(const std::string& e)
{
    double rc = 0.; for (size_t i = e.length(); i--;) rc /= 256., rc += e[i]; return rc;
}
template <> inline unsigned long hashValue(const std::string& e)
{
    unsigned long rc = 0; for (size_t i = 0; i < e.length(); ++i) rc = rc * 13 + e[i]; return rc;
}
template <> std::string nextrandom()
{
    const char* start = helpstr + rand() % sizeof helpstr;
    while (!isalpha(*start)) if (*start) ++start; else start = helpstr;
    const char* end = start + 1;
    while (isalpha(*end)) ++end;
    char buf[10];
    sprintf(buf, "%d", rand() % 1000);
    return std::string(start, end - start) += buf;
}

 // Klasse Person mit allen fГјr die Verwendung als Container-Elementdatentyp noetigen Methoden und Funktionen
 
class Person
{
    std::string vorname;
    std::string nachname;
public:
    Person()
    {
    }
    Person(std::string vorname, std::string nachname) : vorname(vorname), nachname(nachname)
    {
    }
    bool operator==(const Person& p) const
    {
        return vorname == p.vorname && nachname == p.nachname;
    }
    bool operator>(const Person& p) const
    {
        return nachname > p.nachname || (nachname == p.nachname && vorname > p.vorname);
    }

    std::ostream& print(std::ostream& o) const
    {
        return o << '[' << nachname << ", " << vorname << ']';
    }
    std::istream& read(std::istream& i)
    {
        return i >> vorname >> nachname;
    }
    friend double doubleValue<Person>(const Person& e);
    friend unsigned long hashValue<Person>(const Person& e);
    friend unsigned long ordinalValue<Person>(const Person& e);
};
 
inline std::ostream& operator<<(std::ostream& o, const Person& p)
{
    return p.print(o);
}
inline std::istream& operator>>(std::istream& i, Person& p)
{
    return p.read(i);
}
 
 // Template-Spezialisierungen fuer Klasse Person
 
template <> inline double doubleValue(const Person& e)
{
    return doubleValue(e.nachname);
}
template <> inline unsigned long hashValue(const Person& e)
{
    return hashValue(e.nachname);
}
template <> Person nextrandom()
{
    return Person(nextrandom<std::string>(), nextrandom<std::string>());
}
 
bool match(const std::string& s, const char * c)
{
    return c && s.length() <= std::strlen(c) && s.compare(0, s.length(), c, s.length()) == 0;
}
 
int main()
{

    Container<ETYPE>* c = 0;
    bool traceIt = false;
    std::cout.setf(std::ios_base::boolalpha);

    while (true)
    {
        if (traceIt)
        {
            if (c)
            {
                std::cout << std::endl << "container: " << *c;
            }
            else
            {
                std::cout << std::endl << "no container";
            }
        }
        std::cout << std::endl << "> ";

        std::string cmdline;
        if (!std::getline(std::cin, cmdline)) break;

        std::istringstream cmdstream(cmdline);
        std::string cmd;

        cmdstream >> cmd;

        try
        {
            if (cmd.length() == 0)
            {
            }
            else if (match(cmd, "quit"))
            {
                break;
            }
            else if (match(cmd, "new"))
            {
                if (c)
                {
                    std::cerr << "container exists, 'delete' it first";
                }
                else
                {
                    // c = new DoubleHashing<ETYPE,13>;
                    c = new DoubleHashing<ETYPE>;
                }
            }
            else if (match(cmd, "help") || cmd == "?")
            {
                std::cout << helpstr;
            }
            else if (match(cmd, "trace"))
            {
                std::cout << "trace " << ((traceIt = !traceIt) ? "on" : "off");
            }
            else if (!c)
            {
                std::cout << "no container (use 'new')";
            }
            else
            {
                ETYPE key;
                if (match(cmd, "delete"))
                {
                    delete c;
                    c = 0;
                }
                else if (match(cmd, "add"))
                {
                    while (cmdstream >> key)
                    {
                        c->add(key);
                    }
                }
                else if (match(cmd, "remove"))
                {
                    while (cmdstream >> key)
                    {
                        c->remove(key);
                    }
                }
                else if (match(cmd, "member"))
                {
                    cmdstream >> key;
                    std::cout << "returns " << c->member(key);
                }
                else if (match(cmd, "size"))
                {
                    std::cout << "returns " << c->size();
                }
                else if (match(cmd, "empty"))
                {
                    std::cout << "returns " << c->empty();
                }
                else if (match(cmd, "min"))
                {
                    std::cout << "returns " << c->min();
                }
                else if (match(cmd, "max"))
                {
                    std::cout << "returns " << c->max();
                }
                else if (match(cmd, "print"))
                {
                    std::cout << *c;
                }
                else if (match(cmd, "apply"))
                {
                    int n = 0;
                    std::string order = "dontcare";
                    cmdstream >> order >> n;
                    size_t rc = c->apply(PrintN<ETYPE>(n), match(order, "ascending") ? ascending : match(order, "descending") ? descending : dontcare);
                    std::cout << "\nreturns " << rc;
                }
                else if (match(cmd, "fadd"))
                {
                    std::string filename;
                    cmdstream >> filename;
                    std::ifstream keystream(filename.c_str());
                    while (keystream >> key)
                    {
                        c->add(key);
                    }
                }
                else if (match(cmd, "fremove"))
                {
                    std::string filename;
                    cmdstream >> filename;
                    std::ifstream keystream(filename.c_str());
                    while (keystream >> key)
                    {
                        c->remove(key);
                    }
                }
                else if (match(cmd, "radd"))
                {
                    int seed = -1, count = 1;
                    cmdstream >> count >> seed;
                    if (seed != -1) setrandom(seed);
                    while (count-- > 0) c->add(nextrandom<ETYPE>());
                }
                else if (match(cmd, "rremove"))
                {
                    int seed = -1, count = 1;
                    cmdstream >> count >> seed;
                    if (seed != -1) setrandom(seed);
                    while (count-- > 0) c->remove(nextrandom<ETYPE>());
                }
                else
                {
                    std::cout << cmd << "? try 'help'";
                }
            }
        }
        catch (ContainerException& e)
        {
            std::cout << "ContainerException " << e.what();
        }
        catch (std::exception& e)
        {
            std::cout << "Exception " << e.what();
        }
        catch (...)
        {
            std::cout << "OOPS!";
        }
    }
    return 0;
}

2

Re: Подвійне хешування

1. Не зовсім зрозуміло, що саме робить функція add.
2. Процедура пошуку простого числа - ЖАХ. Робіть лінивий масив :)

3

Re: Подвійне хешування

Дякую за швидку відповідь.
1. За допомогою функції add ми додаємо елементи у хеш-таблицю. Можна написати add 1 2 3 4 - і таким чином ми додамо елементи 1, 2, 3 та 4. також є функція radd (n) - вона додає n випадкових елементів у таблицю.
2. Чи не могли б ви показати на прикладі, як краще реалізувати пошук простого числа?

4

Re: Подвійне хешування

1. Краще зробіть функцію, що додає 1 елемент, окремо, і викликайте її в циклі. Більша декомпозиція - менше плутанини. Або розпишіть детальніше, що вона робить, бо там два цикли, створення якихось додаткових масивів, перевірка перед додаванням, яка робить те саме, що й додавання... Я трохи в цьому всьому заплутався - може, не треба там стільки?
2. Кілька простих ідей:
- вже відомі значення простих чисел краще кешувати в масиві, щоб удруге не перевіряти;
- перевіряти треба тільки ділення на прості числа;
- перевіряти треба тільки ділення на числа до кореня з number;
- початок масиву (скажімо, перші 100 чисел) краще одразу додати в програму;
- шукати у впорядкованому масиві можна бінарним пошуком.
3. І винесіть код з .h файлу в .cpp. В .h мають бути тільки проголошення.

5

Re: Подвійне хешування

Дякую за всі поради. Але єдине - код має бути саме у заголовному файлі. Інакше ніяк не можна - такі вимоги.
Якщо у когось будуть ще якісь пропозиції з приводу "прискорення" програми - радо вислухаю!  :)

6 Востаннє редагувалося koala (13.06.2014 13:43:51)

Re: Подвійне хешування

Ось вам перші 10000 простих чисел: http://ideone.com/NQzea2
Працює блискавично :)

Сам код

#include <vector>
#include <iostream>
#include <cmath>

using namespace std;

class Primes
{
  public:
  static Primes *getInstance()
  {
    if( !instance )
      instance = new Primes();
    return instance;
  }
  unsigned int operator[](size_t);
  size_t index(unsigned int);
  size_t closestIndex(unsigned int);
  
  private:
  static Primes *instance;
  Primes()
  {
    unsigned int table[] = { 2, 3, 5 };
    primes.insert( primes.begin(), table, table + sizeof( table ) / sizeof( table[ 0 ] ) );
  }
  vector<unsigned int> primes;
};

Primes *Primes::instance = 0;

unsigned int Primes::operator[]( size_t n )
{
  if( primes.size() <= n )
  {
    unsigned int last = primes[ primes.size() - 1 ];
                  
    while( primes.size() <= n )
    {
      last++;
      unsigned int sqlast = sqrt( last ) + 1;
      bool isPrime = true;
      for( int i = 0; isPrime && ( primes[ i ] <= sqlast ); ++i )
        isPrime = ( ( last % primes[ i ] ) != 0 );
      if( isPrime )
        primes.push_back( last );
    }
  } 
  return primes[ n ];
}

size_t Primes::index(unsigned int p)
{
  size_t search = closestIndex( p );
  return ( (*this)[ search ] == p ) ? search : -1;
}

size_t Primes::closestIndex(unsigned int p)
{
  if( p <= 2 )
    return 0;
  size_t last = primes.size() - 1;

  bool wasSearch = false;

  while( (*this)[ last++ ] < p )
    wasSearch = true;

  last = primes.size() - 1;
  if( primes[ last ] == p )
    return last;
  if( wasSearch )
    return last - 1;

  size_t step = last + 2;
  while( step > 0 )
  {
    step /= 2;
    if( primes[ last ] == p )
      return last;
    if( primes[ last ] > p )
      last -= step;
    else
      last += step;
  }
  return last;
}

int main()

{
  Primes &primes = (*Primes::getInstance());
  for( int i = 0; i < 10000; ++i )
    cout << primes[ i ] << " ";
}

Так, можна було ще пару функцій з algorithm використати, але я вирішив, що так наочніше. Якщо вас vector засмучує - там всього на 5 рядків більше з масивом буде. Повільним лишився тільки корінь; ну і можна трохи оптимізувати перебір (дивитися тільки парні чи 6n±1).

І дуже дивно, що вас змушують код в .h виносити. Це ж гальмує компіляцію!

7

Re: Подвійне хешування

Гм... а які у вас хеш-функції використовуються?

8

Re: Подвійне хешування

hash1 = hashValue(e[i]) % nmax;
hash2 = 1 + (hashValue(e[i]) % (nmax - 2));

9 Востаннє редагувалося koala (14.06.2014 08:02:04)

Re: Подвійне хешування

Я боявся, що ви це скажете, але сподівався, що щось пропустив. hashValue же повертає отримане значення, а nmax == 7? Тобто перший хеш завжди 0..6, а другий 1..5? Вам хтось дуже погано пояснив, нащо потрібні хеш-таблиці - у вас же суцільні колізії by design.
Дивіться, в чому ідея. У нас є купа якихось сутностей (а будь-що в комп'ютері можна вважати числом), які треба шукати по значенню, і якомога швидше - так швидко, що бінарний пошук по впорядкованому масиву вважається повільним (наприклад, значення зберігаються на повільних носіях типу стрімерів, і перевірка кожного значення - це секунди, 5 перевірок - 5 секунд). Якщо числа невеликі і їх мало (скажімо, числа до 10000 і їх 100), то можна створити масив по розміру чисел (тобто з 10000 елементів) і розміщувати ці числа просто в елементах зі своїми номерами: якщо нам треба перевірити, чи є 1234 в таблиці, ми дивимося елемент [1234], і якщо він заповнений - значить, знайшли. Одна перевірка, все дуже швидко, але треба дуже багато пам'яті, і майже вся вона пуста. Звідси походить ідея хешу (англ. to hash - вирубувати, в сенсі "вирубати непотрібні нулі"): нам потрібна функція, яка б перетворювала наші числа у значення, які б розподілялися рівномірно по таблиці, тоді її можна стиснути, повикидавши зайві нулі. Така функція має бути дещо схожою на ГПВЧ - значення мають бути дуже не схожі на початкові, практично випадкові, і при цьому бажано, щоб невелика зміна сутності викликала значну зміну хешу. Ну і звісно що значення хеш-функції мають бути від 0 до розміру таблиці (це досягається залишком від ділення хешу на розмір таблиці, тобто величина хешу має бути значно більшою за розмір таблиці).
Крім того, зі сказаного випливає, що якщо таблиця заповнена наполовину, то ймовірність того, що наступне значення створить колізію, буде 50%, що не дуже добре і таблицю треба розширювати.

10

Re: Подвійне хешування

Дякую за пояснення. Не хотілося б здатися занадто зухвалим, але не могли б ви показати на прикладі, як би ви реалізували хешування у цьому випадку? А то просто я поки що не можу придумати інакшого способу.

11 Востаннє редагувалося koala (13.06.2014 23:06:17)

Re: Подвійне хешування

Спробуйте, скажімо, x^(x>>1)^(x<<1) та x*p+q, де p та q - прості числа.

12

Re: Подвійне хешування

Будь ласка, якщо вирішили свою проблему - викладіть рішення тут для майбутніх поколінь.