Рассмотрим следующий сценарий:
Миллион клиентов посещают магазин и платят деньги с помощью своей кредитной карты. Коды кредитных карт генерируются с использованием 16-значного числа и заменяют 4 его цифры (случайным образом) на символы 'A', 'B', 'C', 'D'. 16-значный номер генерируется случайным образом один раз и используется для каждой кредитной карты, единственное изменение между картами - это позиции в строке вышеупомянутых символов (это ~ 40k возможных различных кодов).
Я должен организовать клиентов в хеш-таблицу, используя выбранную мной хеш-функцию, а также использовать открытую адресацию (линейное зондирование) для устранения коллизий. После того, как организовано в таблице, я должен найти клиента, который
- заплатил больше всего денег за свои покупки.
- больше всего посещал магазин.
Моя реализация хеш-таблицы выглядит следующим образом и, кажется, работает правильно для теста 1000 клиентов. Однако, как только я увеличил количество клиентов до 10000, страница никогда не заканчивает загрузку. Это большая проблема, поскольку общее количество «сессий покупок» должно составлять один миллион, и я даже близко не подхожу к этому числу.
class HashTable{
constructor(size){
this.size = size;
this.items = new Array(this.size);
this.collisions = 0;
}
put(k, v){
let hash = polynomial_evaluation(k);
//evaluating the index to the array
//using modulus a prime number (size of the array)
//This works well as long as the numbers are uniformly
//distributed and sparse.
let index = hash%this.size;
//if the array position is empty
//then fill it with the value v.
if(!this.items[index]){
this.items[index] = v;
}
//if not, search for the next available position
//and fill that with value v.
//if the card already is in the array,
//update the amount paid.
//also increment the collisions variable.
else{
this.collisions++;
let i=1, found = false;
//while the array at index is full
//check whether the card is the same,
//and if not then calculate the new index.
while(this.items[index]){
if(this.items[index] == v){
this.items[index].increaseAmount(v.getAmount());
found = true;
break;
}
index = (hash+i)%this.size;
i++;
}
if(!found){
this.items[index] = v;
}
found = false;
}
return index;
}
get(k){
let hash = polynomial_evaluation(k);
let index = hash%this.size, i=1;
while(this.items[index] != null){
if(this.items[index].getKey() == k){
return this.items[index];
}
else{
index = (hash+i)%this.size;
i++;
}
}
return null;
}
findBiggestSpender(){
let max = {getAmount: function () {
return 0;
}};
for(let item of this.items){
//checking whether the specific item is a client
//since many of the items will be null
if(item instanceof Client){
if(item.getAmount() > max.getAmount()){
max = item;
}
}
}
return max;
}
findMostFrequentBuyer(){
let max = {getTimes: function () {
return 0;
}};
for(let item of this.items){
//checking whether the specific item is a client
//since many of the items will be null
if(item instanceof Client){
if(item.getTimes() > max.getTimes()){
max = item;
}
}
}
return max;
}
}
К ключу, который я использую для вычисления индекса, для массива относится список из 4 целых чисел в диапазоне от 0 до 15, обозначающий позиции 'A', 'B', 'C', 'D' в строке
Вот хэш-функция, которую я использую:
function polynomial_evaluation(key, a=33){
//evaluates the expression:
// x1*a^(d-1) + x2*a^(d-2) + ... + xd
//for a given key in the form of a tuple (x1,x2,...,xd)
//and for a nonzero constant "a".
//for the evaluation of the expression horner's rule is used:
// x_d + a*(x_(d-1) + a(x_(d-2) + .... + a*(x_3 + a*(x_2 + a*x1))... ))
//defining a new key with the elements of the
//old times 2,3,4 or 5 depending on the position
//this helps for "spreading" the values of the keys
let nKey = [key[0]*2, key[1]*3, key[2]*4, key[3]*5];
let sum=0;
for(let i=0; i<nKey.length; i++){
sum*=a;
sum+=nKey[i];
}
return sum;
}
Значения, соответствующие ключам, сгенерированным хэш-функцией, являются экземплярами класса Client, который содержит поля amount (сумма уплаченных денег), times (время покупки данного конкретного клиента), key (массив из 4 целых чисел, упомянутых выше), а также функции-получатели для этих полей. Кроме того, есть метод, который увеличивает amount, когда один и тот же клиент появляется более одного раза.
Размер хеш-таблицы равен 87383 (простое число), и код в моем основном файле выглядит следующим образом:
//initializing the clients array
let clients = createClients(10000);
//creating a new hash table
let ht = new HashTable(N);
for(let client of clients){
ht.put(client.getKey(), client);
}
Это продолжается до тех пор, пока Google Chrome не выдаст сообщение об ошибке «страница не отвечает». Есть ли способ сделать это быстрее? Правильный ли мой подход к предмету (возможно, даже мой выбор языка)?
Заранее спасибо.