Хэш — Основы алгоритмов и структур данных

capitals = [None for _ in range(1873)]

capitals[1804] = "Вена"
capitals[1237] = "Берлин"
capitals[1323] = "Вильнюс"
capitals[1614] = "Тирана"
capitals[1167] = "Копенгаген"
capitals[963] = "Люксембург"
capitals[1067] = "Минск"
capitals[1191] = "Дублин"
capitals[1275] = "Амстердам"
capitals[752] = "Ватикан"
capitals[1786] = "Рейкьявик"
capitals[1200] = "Варшава"
capitals[1872] = "Будапешт"
capitals[856] = "Мадрид"
capitals[1147] = "Москва"

String[] capitals = new String[1873];

capitals[881] = "Вена";
capitals[1237] = "Берлин";
capitals[1323] = "Вильнюс";
capitals[1614] = "Тирана";
capitals[1167] = "Копенгаген";
capitals[963] = "Люксембург";
capitals[1067] = "Минск";
capitals[1191] = "Дублин";
capitals[1275] = "Амстердам";
capitals[752] = "Ватикан";
capitals[1786] = "Рейкьявик";
capitals[1200] = "Варшава";
capitals[1872] = "Будапешт";
capitals[856] = "Мадрид";
capitals[1147] = "Москва";

<?php

$capitals = new SplFixedArray(1873);

$capitals[881] = 'Вена';
$capitals[1237] = 'Берлин';
$capitals[1323] = 'Вильнюс';
$capitals[1614] = 'Тирана';
$capitals[1167] = 'Копенгаген';
$capitals[963] = 'Люксембург';
$capitals[1067] = 'Минск';
$capitals[1191] = 'Дублин';
$capitals[1275] = 'Амстердам';
$capitals[752] = 'Ватикан';
$capitals[1786] = 'Рейкьявик';
$capitals[1200] = 'Варшава';
$capitals[1872] = 'Будапешт';
$capitals[856] = 'Мадрид';
$capitals[1147] = 'Москва';

print(len(capitals))  # => 1873

System.out.println(capitals.length); // => 1873

<?php

print_r(count($capitals)); // => 1873

# В Python для целых чисел используется целочисленное деление
capitals = [None for _ in range(100)];

capitals[1804 // 20] = "Вена"
capitals[1237 // 20] = "Берлин"
capitals[1323 // 20] = "Вильнюс"
capitals[1614 // 20] = "Тирана"
capitals[1167 // 20] = "Копенгаген"
capitals[963 // 20] = "Люксембург"
capitals[1067 // 20] = "Минск"
capitals[1191 // 20] = "Дублин"
capitals[1275 // 20] = "Амстердам"
capitals[752 // 20] = "Ватикан"
capitals[1786 // 20] = "Рейкьявик"
capitals[1200 // 20] = "Варшава"
capitals[1872 // 20] = "Будапешт"
capitals[856 // 20] = "Мадрид"
capitals[1147 // 20] = "Москва"

// В java для целых чисел используется целочисленное деление
String[] capitals = new String[100];

capitals[881 / 20] = "Вена";
capitals[1237 / 20] = "Берлин";
capitals[1323 / 20] = "Вильнюс";
capitals[1614 / 20] = "Тирана";
capitals[1167 / 20] = "Копенгаген";
capitals[963 / 20] = "Люксембург";
capitals[1067 / 20] = "Минск";
capitals[1191 / 20] = "Дублин";
capitals[1275 / 20] = "Амстердам";
capitals[752 / 20] = "Ватикан";
capitals[1786 / 20] = "Рейкьявик";
capitals[1200 / 20] = "Варшава";
capitals[1872 / 20] = "Будапешт";
capitals[856 / 20] = "Мадрид";
capitals[1147 / 20] = "Москва";

<?php

$capitals = new SplFixedArray(100);

$capitals[round(881 / 20)] = 'Вена';
$capitals[round(1237 / 20)] = 'Берлин';
$capitals[round(1323 / 20)] = 'Вильнюс';
$capitals[round(1614 / 20)] = 'Тирана';
$capitals[round(1167 / 20)] = 'Копенгаген';
$capitals[round(963 / 20)] = 'Люксембург';
$capitals[round(1067 / 20)] = 'Минск';
$capitals[round(1191 / 20)] = 'Дублин';
$capitals[round(1275 / 20)] = 'Амстердам';
$capitals[round(752 / 20)] = 'Ватикан';
$capitals[round(1786 / 20)] = 'Рейкьявик';
$capitals[round(1200 / 20)] = 'Варшава';
$capitals[round(1872 / 20)] = 'Будапешт';
$capitals[round(856 / 20)] = 'Мадрид';
$capitals[round(1147 / 20)] = 'Москва';

def get_city(year):
    return capitals[year // 20]

city = get_city(1191)  # Дублин

class App {
    public static String getCity(String[] capitals, int year) {
        return capitals[year / 20];
    }
}

<?php

function getCity($year, $capitals)
{
    return $capitals[round($year / 20)];
}

capitals = [None for _ in range(100)]

String[] capitals = new String[100];

<?php

$capitals = array_fill(0, 100, null);

print(1999 % 20)  # => 19

System.out.println(1999 % 20); // => 19

<?php

print_r(1999 % 20); // => 19

capitals = [None for _ in range(100)]

capitals[1804 % 100] = 'Вена'
capitals[1237 % 100] = 'Берлин'
capitals[1323 % 100] = 'Вильнюс'
capitals[1614 % 100] = 'Тирана'
capitals[1167 % 100] = 'Копенгаген'
capitals[963 % 100] = 'Люксембург'
capitals[1067 % 100] = 'Минск'
capitals[1191 % 100] = 'Дублин'
capitals[1275 % 100] = 'Амстердам'
capitals[752 % 100] = 'Ватикан'
capitals[1786 % 100] = 'Рейкьявик'
capitals[1200 % 100] = 'Варшава'
capitals[1872 % 100] = 'Будапешт'
capitals[856 % 100] = 'Мадрид'
capitals[1147 % 100] = 'Москва'

def get_city(year):
    return capitals[year % 100]

city = get_city(1167)  # Копенгаген

String[] capitals = new String[100];

capitals[881 % 100] = "Вена";
capitals[1237 % 100] = "Берлин";
capitals[1323 % 100] = "Вильнюс";
capitals[1614 % 100] = "Тирана";
capitals[1167 % 100] = "Копенгаген";
capitals[963 % 100] = "Люксембург";
capitals[1067 % 100] = "Минск";
capitals[1191 % 100] = "Дублин";
capitals[1275 % 100] = "Амстердам";
capitals[752 % 100] = "Ватикан";
capitals[1786 % 100] = "Рейкьявик";
capitals[1200 % 100] = "Варшава";
capitals[1872 % 100] = "Будапешт";
capitals[856 % 100] = "Мадрид";
capitals[1147 % 100] = "Москва";

class App {
    public static String getCity(String[] capitals, int year) {
        return capitals[year % 100];
    }
}

<?php

$capitals = array_fill(0, 100, null);

$capitals[881 % 100] = 'Вена';
$capitals[1237 % 100] = 'Берлин';
$capitals[1323 % 100] = 'Вильнюс';
$capitals[1614 % 100] = 'Тирана';
$capitals[1167 % 100] = 'Копенгаген';
$capitals[963 % 100] = 'Люксембург';
$capitals[1067 % 100] = 'Минск';
$capitals[1191 % 100] = 'Дублин';
$capitals[1275 % 100] = 'Амстердам';
$capitals[752 % 100] = 'Ватикан';
$capitals[1786 % 100] = 'Рейкьявик';
$capitals[1200 % 100] = 'Варшава';
$capitals[1872 % 100] = 'Будапешт';
$capitals[856 % 100] = 'Мадрид';
$capitals[1147 % 100] = 'Москва';

const getCity = (year) => $capitals[year % 100];

function getCity($capitals, $year)
{
    return $capitals[$year % 100];
}

$city = getCity(1167); // 'Копенгаген'

print(get_city(1167))  # => Минск

System.out.println(App.getCity(1167)); // => Минск

<?php

print_r(getCity(1167)); // => Минск

from LinkedList import LinkedList

capitals = [None for _ in range(100)]

def set_capital(year, city):
    index = year % len(capitals)

    if capitals[index] is None:
        capitals[index] = LinkedList()

    capitals[index].add({'key': year, 'value': city})

class App {
    private LinkedList[] capitals = new LinkedList[100];

    public void setCapital(int year, String city) {
        var index = year % capitals.length;
        if (capitals[index] == null) {
            capitals[index] = new LinkedList<Object[]>();
        }

        capitals[index].add(new Object[] {year, city});
    }
}

<?php

use LinkedList;

$capitals = array_fill(0, 100, null);

function setCapital($year, $city, &$capitals)
{
    $index = $year % count(capitals);
    if (!isset($capitals[$index])) {
        $capitals[$index] = new LinkedList();
    }

    $capitals[$index]->add(['key' => $year, 'value' => $city]);
}

def get_capital(year):
    index = year % len(capitals)

    if capitals[index] is None:
        return None

    for pair in capitals[index]:
        if pair['key'] == year:
            return pair['value']

    return None

lass App {
    private LinkedList[] capitals = new LinkedList[100];

    public void setCapital(int year, String city) {
        // ...
    }

    public String getCapital(int year) {
        var index = year % capitals.length;

        if (capitals[index] == null) {
            return null;
        }

        for (var pair : capitals[index]) {
            var casted = (Object[]) pair;
            if ((int) casted[0] == year) {
                return (String) casted[1];
            }
        }

        return null;
    }
}

<?php

function getCapital($capitals, $year)
{
  $index = $year % count($capitals);
  if (!isset($capitals[$year])) {
      return null;
  }

  foreach($capitals[$index] as $pair) {
      if ($pair['key'] === $year) {
          return $pair['value'];
      }
  }

  return null;
}

capital = 'Мадрид'

for i in range(len(capital)):
    print(ord(capital[i]))
# => 1052
# => 1072
# => 1076
# => 1088
# => 1080
# => 1076

var capital = "Мадрид";
for (var i = 0; i < capital.length; i++) {
    System.out.println((int) capital.charAt(i));
}
// => 1052
// => 1072
// => 1076
// => 1088
// => 1080
// => 1076

<?php

$capital = 'Мадрид';
for ($i = 0; $i < count($capital); i += 1) {
  print_r(mb_ord($capital[$i]));
}
// => 1052
// => 1072
// => 1076
// => 1088
// => 1080
// => 1076

def hash(s):
    k = 65537
    m = 2**20

    result = 0
    k_i = 1

    for i in range(len(s)):
        result = (result + k_i * ord(s[i])) % m
        k_i = (k_i * k) % m

    return result

class App {
    private int hash(String s) {
        var k = 65537;
        var m = (int) Math.pow(2, 20);

        var result = 0;
        var k_i = 1;

        for (var i = 0; i < s.length(); i++) {
            result = (result + k_i * s.charAt(i)) % m;
            k_i = (k_i * k) % m;
        }

        return result;
    }
}

<?php

function hash($s)
{
    $k = 65537;
    $m = 2 ** 20;

    $result = 0;
    $k_i = 1;
    for ($i = 0; $i < mb_strlen($s); $i += 1) {
        $result = ($result + $k_i * mb_ord($s[$i])) % $m;
        $k_i = ($k_i * $k) % $m;
    }

    return $result;
}

hash('Мадрид') # 792876
hash('Москва') # 399671
hash('Минск')  # 857356

App.hash("Мадрид") // 792876
App.hash("Москва") // 399671
App.hash("Минск")  // 857356

<?php

hash('Мадрид') // 792876
hash('Москва') // 399671
hash('Минск')  // 857356

class Hash:
    table = []
    count = 0

    def hash(self, s):
        k = 65537
        m = 2**20

        result = 0
        power = 1

        for i in range(len(s)):
            result = (result + power * ord(s[i])) % m
            power = (power * k) % m

        return result

    def calculate_index(self, table, key):
        try:
            return self.hash(str(key)) % len(table)
        except ZeroDivisionError:
            return self.hash(str(key))

    def rebuild_table_if_need(self):
        if len(self.table) == 0:
            table = [None for _ in range(128)]
        else:
            load_factor = self.count / len(self.table)

            if load_factor >= 0.8:
                new_table = [None for _ in range(len(self.table) * 2)]

                for list_ in self.table:
                    for pair in list_:
                        new_index = self.calculate_index(new_table, pair['key'])
                        if new_table[new_index] is None:
                            new_table[new_index] = LinkedList()

                        new_table[new_index].add(pair)

                self.table = new_table

    def set(self, key, value):
        self.rebuild_table_if_need()
        index = self.calculate_index(self.table, key)

        if self.table[index] is None:
            self.table[index] = LinkedList()

        self.table[index].add(
            {'key': key, 'value': value}
        )
        self.count += 1

    def get(self, key):
        index = self.calculate_index(self.table, key)

        if self.table[index] is None:
            return None

        for pair in self.table[index]:
            if pair['key'] == key:
                return pair['value']

        return None

public class Hash {

    public LinkedList[] table = new LinkedList[128];
    public int count = 0;

    private int hash(String s) {
        var k = 65537;
        var m = (int) Math.pow(2, 20);

        var result = 0;
        var k_i = 1;

        for (var i = 0; i < s.length(); i++) {
            result = (result + k_i * s.charAt(i)) % m;
            k_i = (k_i * k) % m;
        }

        return result;
    }

    public int calculateIndex(LinkedList[] table, String key) {
        return hash(key) % table.length;
    }

    private void rubuildTableIfNeed() {
        var loadFactor = (double) count / table.length;
        if (loadFactor >= 0.8) {
            LinkedList[] newTable = new LinkedList[table.length * 2];
            for (LinkedList list : table) {
                for (var pair : list) {
                    Object[] casted = (Object[]) pair;
                    var newIndex = calculateIndex(newTable, (String) casted[0]);
                    if (newTable[newIndex] == null) {
                        newTable[newIndex] = new LinkedList();
                    }

                    newTable[newIndex].append(pair);
                }
            }

            table = newTable;
        }
    }

    public void set(String key, Object value) {
        this.rubuildTableIfNeed();
        var index = calculateIndex(table, key);

        if (table[index] == null) {
            table[index] = new LinkedList();
        }

        table[index].append(new Object[] {key, value});
        count++;
    }

    public Object get(String key) {
        var index = calculateIndex(table, key);
        if (table[index] == null) {
            return null;
        }

        for (var current : table[index]) {
            LinkedListNode node = (LinkedListNode) current;
            var pair = node.value;
            var casted = (Object[]) pair;
            if (casted[0].equals(key)) {
                return casted[1];
            }
        }

        return null;
    }
}

<?php

class Hash
{
    public function __construct()
    {
        $this->table = [];
        $this->count = 0;
    }

    public function hash($s)
    {
        $k = 65537;
        $m = 2 ** 20;

        $result = 0;
        $power = 1;
        for ($i = 0; $i < strlen($s); $i += 1) {
            $result = ($result + $power * ord($s[$i])) % $m;
            $power = ($power * $k) % $m;
        }

        return $result;
    }

    public function calculateIndex($table, $key)
    {
        return $this->hash((string) $key) % count($table);
    }

    public function rebuildTableIfNeed()
    {
        if (count($this->table) === 0) {
            $this->table = array_fill(0, 128, null);
        } else {
            $loadFactor = $this->count / count($this->table);
            if ($loadFactor >= 0.8) {
                $newTable = array_fill(0, count($this->table) * 2, null);
                foreach ($this->table as $list) {
                    foreach ($list as $pair) {
                        $newIndex = $this->calculateIndex($newTable, $pair['key']);
                        if (!isset($newTable[$newIndex])) {
                            $newTable[$newIndex] = new LinkedList();
                        }

                        $newTable[$newIndex]->append($pair);
                    }
                }

                $this->table = $newTable;
            }
        }
    }

    public function set($key, $value)
    {
        $this->rebuildTableIfNeed();

        $index = $this->calculateIndex($this->table, $key);
        if (!isset($this->table[$index])) {
            $this->table[$index] = new LinkedList();
        }

        $this->table[$index]->append(['key' => $key, 'value' => $value ]);
        $this->count += 1;
    }

    public function get($key)
    {
        $index = $this->calculateIndex($this->table, $key);
        if (!isset($this->table[$index])) {
            return null;
        }

        foreach ($this->table[$index] as $pair1) {
            $pair = (array) $pair1;
            if ($pair['value']['key'] === $key) {
                return $pair['value']['value'];
            }
        }

        return null;
    }
}

new_table = [None for _ in range(len(self.table) * 2)]

for list_ in self.table:
    for pair in list_:
        new_index = self.calculate_index(new_table, pair['key'])
        if new_table[new_index] is None:
            new_table[new_index] = LinkedList()

        new_table[new_index].add(pair)

LinkedList[] newTable = new LinkedList[table.length * 2];

for (LinkedList list : table) {
    for (var pair : list) {
        Object[] casted = (Object[]) pair;
        var newIndex = calculateIndex(newTable, (String) casted[0]);
        if (newTable[newIndex] == null) {
            newTable[newIndex] = new LinkedList();
        }

        newTable[newIndex].add(pair);
    }
}

<?php

$newTable = array_fill(0, count($this->table) * 2, null);
foreach ($this->table as $list) {
    foreach ($list as $pair) {
        $newIndex = $this->calculateIndex($newTable, $pair['key'])
        if (!isset($newTable[$newIndex])) {
            $newTable[$newIndex] = new LinkedList();
        }

      $newTable[$newIndex]->add($pair);
    }
}