Методи хешування

1. Метод ділення:

1.1. Значення ключа – ціле додатне число (або ключ можна легко представити таким числом);

1.2. Дільник – просте число далеке від степені двійки.

Індекс вичислюється шляхом застосування операції отримання залишку від ділення значення ключа на розмірність хеш-таблиці.

2. Метод множення:

2.1. Значення ключа – дійсне число з діапазону від 0 до 1;

2.2. Множник – значення рівне степені двійки.

Індекс розраховується за наступним алгоритмом:

А) ключ множиться на константу з діапазону від 0 до 1 для виділення дрібної частини (0,6180339887);

Б) отримане значення множиться на розмірність хеш-таблиці і округляється до найменшого цілого.

3. Метод універсального хешування:

Індекс обчислюється з використанням хеш-функції, що випадково обирається з деякого відібраного класу функцій.

· Третє:

1. Всі об’єкти зберігаються безпосередньо у хеш-таблиці.

2. Для розрахунку індексу використовуються хеш-функції.

3. Для розв’язку колізій визначається послідовність елементів, серед яких знаходиться пустий елемент.

class Obj {

int x;

int y;

Obj next;

Obj(int a, int b) { x=a; y=b; }

public int hashCode() { return ((x<<1) + y); }

public boolean equals(Object o) {

return (x == ((Obj)o).x)&&(y == ((Obj)o).y); }

public String toString() {

return (String.valueOf(x) + " " + String.valueOf(y)); }

}

class Table {

Obj mas[];

Table(int r) {mas = new Obj [r]; }

private int Code(Obj o) {

return (o.hashCode() % mas.length); }

private void Col(Obj cur, Obj n_ob) {

while ((cur!= null) && (!cur.equals(n_ob)))

if (cur.next == null) {

cur.next = n_ob; break;

}

else cur = cur.next;

}

public void ins(Obj new_ob) {

int h = Code(new_ob);

if (mas[h] == null) mas[h] = new_ob;

else Col(mas[h], new_ob);

}

public void prin() {

for(int i=0; i<mas.length; i++) {

Obj temp = mas[i];

System.out.print(i +") ");

while (temp!= null) {

System.out.print(temp + "; ");

temp = temp.next;

}

System.out.println();

}

}

}

public class HashDemo {

public static void main(String [] args) {

Scanner in = new Scanner(System.in);

int a, b;

System.out.print("Enter size HashTable -> ");

Table hash = new Table(in.nextInt());

while(true) {

System.out.print("\nAdd the object? Yes - press key 'y', No - press any key ");

if (in.next().equals("y")) {

System.out.print("Enter value elememt -> a and b ");

a = in.nextInt();

b = in.nextInt();

hash.ins(new Obj(a, b));

}else break;

}

System.out.println("\nHashTable");

hash.prin();

}

}

Способи:

1. Лінійне зондування: М[i+p], де р=1,2,3…; послідовно проглядаються усі наступні комірки з переходом з останньої на першу;

2. Квадратичне зондування: М[i+p^2], де р=1,2,3…; послідовно проглядаються усі елементи з квадратичним зміщенням і з переходом з останньої на першу;

3. Подвійне зондування: М[i+f(p)], p=1,2,3… f(p)=p*hl(key); зміщення від знайденого елементу вираховується за допомогою хеш-функції;

4. Ідеальне зондування: М[i][hl(key)] двовимірний масив і дві хеш-функції.

Сортування – це процес упорядкування деяких даних у відповідності деяким визначеним критеріям (правилам)

Випадки сортування:

1. У використанні до самих даних

2. У використанні до кроків, асоційованих з даними (до ключів)

Група методів сортування:

1. Елементарне сортування

2. Методи швидкого сортування

3. Методи злиття і сортування злиттям

4. Методи пірамідального сортування

5. Методи порозрядного сортування

Елементарні методи сортування

1. Сортування методом вибору

2. Методи вставки

3. Методи бульбашки

4. Метод Шелла

5. По індексам вказівника

6. Метод розподіленого підрахунку

Поиск по сайту: