Java. Урок 32. Ассоциативные массивы

Уроки для начинающих   15 Февраль 2013  Автор статьи:  

А у вас никогда не возникало желание обращаться к массиву не через индекс, а по любому ключу? Вот допустим у нас есть студент, мы знаем про него много информации, но все данные про студентов хранятся в массиве, тогда достать информацию из мы массива можем только по его номеру, поэтому нам приходиться пробегать весь массив, если мы знаем например только его имя или что — то еще. И встает вопрос как сделать так, чтобы можно было обращаться не только по целочисленному значению в массив, а по любому ключу. Например мы хотим получать всех пользователей по их логину, а не по волшебному номеру, который и сам пользователь то не знает. Очевидно, что логин это строка, и что мы не можем более менее нормально обеспечивать доступ к информации быстрее чем за O(N) с применением массива, тогда на помощь к нам приходит ассоциативный массив. Ассоциативный массив прекрасен тем, что может работать с любым ключом, будь то сложный объект или строка. Для чего это нужно? Во первых мы не храним никакой избыточной информации, у нас есть только реально существующие элементы в массиве. Т.е мы, например бы могли брать создавать достаточно большой массив, брать хеш код у любого объекта и по нему класть в массив, что обеспечила нам бы работу с любыми ключами, так как известно что хеш функцию с тем или иным успехом можно составить для любого объекта. Но тогда бы у нас и возникли пустые места. После прочтения выше написанного, у вас, возможно, сложилось мнение, что ассоциативные массивы это круто и видимо решают достаточно большой класс задач, но на самом деле не все так просто. В зависимости от реализации ассоциативные массивы выполняют операции за время отличное от константы. Но уже хватит говорить об них, давайте рассмотрим интерфейс для работы с ассоциативными массивами.

Интерфейс Map

При создании Интерфейса Map указывают тип ключа и значения:

1
Map<Integer, String> map;//Map<K,V>

Тип данных ключа будем обозначать K, а значения V.

  • size() — возвращает количество элементов
  • containsKey(Object key) — проверяет наличие ключа
  • containsValue(Object value) — проверяет наличие значения в ассоциативном массиве
  • get(Object key) — возвращает значение по ключу
  • put(K key, V value) — кладет в ассоциативный массив значение value по ключу key. В случае наличия уже такого ключа происходит замена значения.
  • values() — возвращает значения всех элементов в виде коллекции
  • remove(Object key) — удаляет элемент с ключом key, возвращая значение этого элемента(вернет null в случае отсутствия)
  • clear() — удаляет все элементы из массива
  • isEmpty() — возвращает не пуст ли массив
Hashtable

Hashtable — реализация интерфейса Map, основанная на хеш-таблицах. Не гарантирует какое — то определенное время выполнения, но в среднем работает за O(1). Тут следует сказать, что хеш-таблицы имеют два важных параметра: capacity (максимальное количество элементов) и loadFactor (загруженность таблицы). При достижении количества реально существующих элементов в размере 0,75 от максимального происходит автоматическое увеличение максимального количество элементов, т.е самой таблицы. 0,75 это показатель по умолчанию, конечно вы можете изменить загруженность таблицы:

1
2
Map<Integer, String> map = new Hashtable<Integer, String>(100, (float) 0.5);//создаем таблицу с максимальным размером в 100 элементов
//и с загруженностью 0.5

Кроме этого, существует класс HashMap, который имеет схожую функциональность, но при работе с потоками его лучше не использовать.

TreeMap

TreeMap — реализация интерфейса Map, основанная на деревьях. Как и в любом дереве операции взятия элемента по ключу, вставка или удаления происходят за O(logN). Пример использования TreeMap:

1
Map<String, String> map = new TreeMap<String, String>();

С основными реализациями ассоциативного массива мы закончили, давайте попробуем реализовать пример про студентов. Т.е у нас есть некоторый класс Student:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
package ru.cybern;
public class Student {
    private int number;//номер студенческого билета
    private String name;//имя студента
    private int age;//возраст

    @Override
    public boolean equals(Object o) {//переопределяем метод equals
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Student student = (Student) o;

        if (age != student.age) return false;
        if (number != student.number) return false;
        if (name != null ? !name.equals(student.name) : student.name != null) return false;

        return true;
    }

    @Override
    public int hashCode() {//переопределяем метод hashCode
        int result = number;
        result = 31 * result + (name != null ? name.hashCode() : 0);
        result = 31 * result + age;
        return result;
    }

    public int getNumber() {

        return number;
    }

    public void setNumber(int number) {
        this.number = number;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public Student(int number, String name, int age) {
        this.number = number;
        this.name = name;
        this.age = age;
    }
    public String toString() {
        return "Student{" +
                "number=" + number +
                ", name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

Когда я создавал этот класс, я написал только три поля, все остальное автоматически генерировала среда intellij idea, что полностью оправдывает ее название. Напоминаю, для того, чтобы пользоваться автоматической генерацией кода нажмите одновременно alt+insert, а затем выберите объект, который хотите генерировать, кроме стандартных get и set, а также конструктора, я добавил equals,hashCode и toString. Эта процедура может понадобиться для того, чтобы использовать hashTable, дело в том, что для генерации хеша, данный класс использует вызов стандартной функции hashCode, которая по умолчанию для пользовательских объектов (унаследованных от класса object) возвращает адрес, т.е возникает такая же ситуация, как и со строками, если их сравнивать через ==. Напишем класс Test, в котором просто создадим ассоциативный массив, и попробуем добавить туда некоторое количество элементов, а затем будем пытаться получать студентов по их имени:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
package ru.cybern;

import java.util.Hashtable;
import java.util.Map;

public class Test {
    public void test()
    {
        Map<String, Student> map = new Hashtable<String, Student>();
        Student st = new Student(0,"Alex", 18);
        map.put("Alex", st);//добавляю студента Alex по ключу Alex
        System.out.println(map.get("Alex"));//работает
        System.out.println(map.get("Al" + "ex"));  //работает
        System.out.println(map.get(st.getName()));//работает
        String s = "a";//пытаюсь обмануть компилятор
        s = s.toUpperCase()+"lex";
        System.out.println(map.get(s)); //работает
    }
}

  • alex99orel

    А что за интерфейс Map? Много чего не понятно

    • http://cybern.ru/ lordrp

      Что именно. Задавайте вопросы, я отвечу.

      • alex99orel

        Ну, например, мне очень интересно, что такое ХэшКод.

        • http://cybern.ru/ lordrp

          У нас есть такая фича, называется термины. Они должны подцепляться к статье и если значит есть слово у нас в терминах, то автоматически ставится ссылка. И вот значит, к чему я, вообще на всех непонятных штуках будут ссылки на другие статьи, где этот слово будет полностью раскрываться. И раньше у нас еще был поиск по сайту, который пока мы не успели восстановить… Ну собственно говоря статьи по хеш — это результат работы хеш функции. http://cybern.ru/hash-function.html

        • http://cybern.ru/ lordrp

          Что еще не понятно?

  • ktotam

    Написано: «достать информацию из мы массива можем»
    Исправить: «достать информацию из массива мы можем»

Научиться программировать

  • на Delphi

  • на Java

  • на C++