hashed array tree

Angol

Főnév

hashed array tree (tsz. hashed array trees)

1. (informatika) A Hashed Array Tree (HAT) egy dinamikus tömbszerkezet, amely a dinamikus tömbök (pl. std::vector) és a láncolt listák közötti kompromisszumot kínál. A célja, hogy: - Gyorsítja a beszúrást (O(1) amortizált) - Hatékonyabbá teszi a memóriafelhasználást - Kiegyensúlyozza az indexelést és a növekedést

---

1. Hogyan működik a Hashed Array Tree?

A Hashed Array Tree egy kétlépcsős tömbstruktúra: - Van egy fő tömb (top-level array), amely mutatókat tartalmaz alsó szintű tömbökre (leaf arrays). - Minden alsó szintű tömb egy rögzített méretű tömb. - Ha az alsó tömbök betelnek, az egész struktúra dinamikusan bővül.

✅ O(1) indexelés (közvetlen elérés)
✅ O(1) amortizált beszúrás
✅ Memóriahatékonyabb mint a hagyományos dinamikus tömbök

---

2. Hashed Array Tree implementáció C++-ban

Az alábbi implementáció egy Hashed Array Tree (HAT) adatszerkezetet valósít meg.

#include <iostream>
#include <vector>

class HashedArrayTree {
private:
    std::vector<std::vector<int>> table; // Felső szintű tömb (mutatók alsó tömbökre)
    int capacity;  // Maximális elemszám a struktúrában
    int size;      // Jelenlegi elemszám
    int leafSize;  // Az egyes alsó tömbök mérete

public:
    // Konstruktor
    HashedArrayTree(int leafSize = 4) : size(0), capacity(leafSize), leafSize(leafSize) {
        table.resize(1);
        table[0].resize(leafSize);
    }

    // Új elem beszúrása
    void insert(int value) {
        if (size == capacity) {
            expand();
        }
        int row = size / leafSize;  // Melyik alsó tömbbe kerül?
        int col = size % leafSize;  // Az alsó tömb melyik indexére?

        table[row][col] = value;
        size++;
    }

    // Kiterjesztés új alsó szintű tömbbel
    void expand() {
        capacity *= 2;  // Duplázza a kapacitást
        table.push_back(std::vector<int>(leafSize));  // Új alsó tömb hozzáadása
    }

    // Indexelés (O(1))
    int get(int index) {
        if (index < 0 || index >= size) {
            throw std::out_of_range("Index kívül esik a tartományon.");
        }
        int row = index / leafSize;
        int col = index % leafSize;
        return table[row][col];
    }

    // Méret visszaadása
    int getSize() const {
        return size;
    }

    // Kiíratás
    void print() {
        std::cout << "Hashed Array Tree elemei:\n";
        for (int i = 0; i < size; i++) {
            std::cout << get(i) << " ";
        }
        std::cout << "\n";
    }
};

// Főprogram
int main() {
    HashedArrayTree hat(4); // Minden alsó tömb mérete 4

    // Beszúrások
    hat.insert(10);
    hat.insert(20);
    hat.insert(30);
    hat.insert(40); // Első alsó tömb megtelt
    hat.insert(50); // Új alsó tömb létrejön

    hat.print();

    // Egy elem elérése
    std::cout << "3. elem: " << hat.get(3) << "\n";

    return 0;
}

Kimenet:

Hashed Array Tree elemei:
10 20 30 40 50 
3. elem: 40

---

3. Hashed Array Tree vs. std::vector vs. std::deque

Adatszerkezet	Indexelés	Beszúrás (vége)	Beszúrás (eleje)	Memóriahatékonyság
std::vector	O(1)	O(1) amortizált	O(N)	Kiegyensúlyozott
std::deque	O(1)	O(1) amortizált	O(1) amortizált	Magasabb overhead
Hashed Array Tree	O(1)	O(1) amortizált	O(N)	Jobb memória kezelés

✅ Hashed Array Tree előnyei: - Gyors beszúrás és indexelés O(1) időben. - Kevesebb újraallokáció nagy adatszerkezeteknél. - Nem szükséges egyetlen nagy, folyamatos memóriaterület.

További információk

• hashed array tree - Szótár.net (en-hu)
• hashed array tree - Sztaki (en-hu)
• hashed array tree - Merriam–Webster
• hashed array tree - Cambridge
• hashed array tree - WordNet
• hashed array tree - Яндекс (en-ru)
• hashed array tree - Google (en-hu)
• hashed array tree - Wikidata
• hashed array tree - Wikipédia (angol)