VI Международная студенческая научная конференция Студенческий научный форум - 2014

Цель исследования: обзор 3-х разных хеш-функций (3 способа хеширования) и оценить для каждой свойства. На основе данных (50 фамилий и имен) выполнить оценку синонимов (коллизий) и измерение скорость выполнения хеш-функции.

Выполнение:

Первая хеш – функция HashTable. Реализация хеш функции на С++.

Листингпрограммы:

class Identifier

{

public:

Identifier(const std::string& name):

m_name(name)

{

}

public:

std::string name() const

{

return m_name;

}

private:

std::string m_name;

};

bool operator==(const Identifier& left, const Identifier& right)

{

return left.name() == right.name();

}

size_t hash(const Identifier& id)

{

return size_t(id.name()[0]);

}

class IDNotFoundException : std::exception

{

public:

IDNotFoundException(const std::string id_name):

m_what(std::string("Identifier '") + id_name + "' not found!")

{

}

virtual ~IDNotFoundException() throw()

{

}

public:

const char *what() const throw()

{

return m_what.c_str();

}

private:

std::string m_what;

};

class HashTable

{

public:

static const size_t min_hash_value = int('0');

static const size_t max_hash_value = int('z');

static const size_t hash_table_size = max_hash_value - min_hash_value;

public:

void add(const Identifier& id)

{

m_hash_table[hash(id) - min_hash_value].push_back(id);

}

Identifier& get(const std::string& id_name)

{

std::list& line = m_hash_table[hash(id_name) - min_hash_value];

std::list::iterator it =

std::find(line.begin(), line.end(), id_name);

if (it == line.end())

throw IDNotFoundException(id_name);

return *it;

}

size_t collisions_count() const

{

size_t result = 0;

for (size_t i = 0; i < hash_table_size; ++i)

if (m_hash_table[i].size() > 1)

++result;

return result;

}

private:

std::list m_hash_table[hash_table_size];

};

int main()

{

clock_t start = clock();

size_t result;

setlocale(LC_ALL, "rus");

HashTable ht;

ht.add(Identifier("Abramson Hoggarth"));

ht.add(Identifier("Adamson Holiday"));

ht.add(Identifier("Adderiy Holmes"));

ht.add(Identifier("Adrian Howard"));

ht.add(Identifier("Allford Jenkin"));

ht.add(Identifier("Atcheson Kendal"));

ht.add(Identifier("Adrian Howard"));

ht.add(Identifier("Charlson Nash"));

ht.add(Identifier("AbramsonDean Owen"));

ht.add(Identifier("Dodson Palmer"));

ht.add(Identifier("Adderiy Donaldson"));

ht.add(Identifier("Dowman Parson"));

ht.add(Identifier("Allford Jenkin"));

ht.add(Identifier("Douglas Kendal"));

ht.add(Identifier("Dutton Howard"));

ht.add(Identifier("Dodson Nash"));

ht.add(Identifier("Farmer Hoggarth"));

ht.add(Identifier("Ferguson Holiday"));

ht.add(Identifier("Fitzgerald Holmes"));

ht.add(Identifier("Daniels Howard"));

ht.add(Identifier("Duncan Jenkin"));

ht.add(Identifier("Eddington Kendal"));

ht.add(Identifier("Hailey Howard"));

ht.add(Identifier("Derrick Nash"));

ht.add(Identifier("Ayrton Owen"));

ht.add(Identifier("Barnes Palmer"));

ht.add(Identifier("Barrington Donaldson"));

ht.add(Identifier("Baldwin Parson"));

ht.add(Identifier("Hodges Jenkin"));

ht.add(Identifier("Haig Kendal"));

ht.add(Identifier("Goldman Howard"));

ht.add(Identifier("Fulton Nash"));

ht.add(Identifier("Bishop Howard"));

ht.add(Identifier("Black Nash"));

ht.add(Identifier("Barrington Hoggarth"));

ht.add(Identifier("Croftoon Holiday"));

ht.add(Identifier("Crossman Holmes"));

ht.add(Identifier("Davidson Howard"));

ht.add(Identifier("Day Jenkin"));

ht.add(Identifier("Evans Kendal"));

ht.add(Identifier("Farrell Howard"));

ht.add(Identifier("Fulton Nash"));

ht.add(Identifier("Carroll Owen"));

ht.add(Identifier("Donovan Palmer"));

ht.add(Identifier("Harrison Donaldson"));

ht.add(Identifier("Croftoon Parson"));

ht.add(Identifier("Cook Jenkin"));

ht.add(Identifier("Bradberry Kendal"));

ht.add(Identifier("Blomfield Howard"));

ht.add(Identifier("Ayrton Nash"));

try

{

std::cout

Код для цитирования: Скопировать