Звучит знакомо? но мы собираемся присмотреться.
Они представляют собой набор пар "ключ-значение", в который мы можем вставить значение с определенным ключом и искать значение по этому ключу. Также известны как карты, словари или ассоциативные массивы.
Таблицы символов
Основные операции таблицы символов: положить, получить, удалить, contains & isEmpty.
Операция put вставляет пару "ключ-значение" в таблицу (удаляет ключ из таблицы, если значение равно null), get возвращает значение с данным ключом (null, если не существует) , delete удаляет ключ и его значение из таблицы, а contains проверяет, существует ли значение, связанное с данным ключом.
Условные обозначения в таблице символов
Есть несколько вариантов, которые мы сделали для наших реализаций, чтобы сделать наш код последовательным и полезным.
- Дженерики
Тип ключа и значения - это любой общий тип.
- Повторяющиеся ключи
С каждым ключом связано только одно значение (в таблице нет повторяющихся ключей).
Это соглашение напрямую связано с операцией put; заменяет старое значение новым значением, если этот ключ уже существует в таблице.
- Нулевые значения
Никакой ключ не может быть связан со значением null.
Это соглашение напрямую связано с операцией get; возвращает null для ключей, отсутствующих в таблице. (Предполагаемые) последствия отсутствия нулевых значений:
- Мы можем проверить, существует ли ключ или нет, проверив, возвращает ли get значение null.
- Мы можем реализовать ленивую версию delete, вызвав put, передав в качестве значения null.
- Удаление
Удаление в таблицах символов обычно включает одну из двух стратегий: ленивое удаление, когда мы связываем ключи в таблице с нулем (как мы только что сказали), затем, возможно, удаляем все такие ключи позже, и нетерпеливое удаление, при котором мы немедленно удаляем ключ из таблицы.
- Итераторы
Мы можем перебирать ключи в таблице. Это можно сделать, определив метод, например, с именем keys (), который возвращает объект Iterable.
- Тип ключей
В зависимости от реализации есть несколько разных предположений:
[1] Ключи сопоставимы
Итак, мы можем использовать метод compareTo (), чтобы сравнить, является ли один ключ меньше другого, или больше, или равный.
Таким образом, мы можем получить более эффективную реализацию, которая поможет нам ориентироваться в структуре данных и будет поддерживать более широкий набор простых табличных операций, которые очень удобны для многих клиентов.
public class ST<Key extends Comparable<Key>, Value> { /* ... */ }
// string class must implement Comparable interface
ST<String, Integer> st = new ST<String, Integer>();
[2] Ключи реализуют метод equals ()
В других ситуациях, возможно, они не сопоставимы, и все, что нам разрешено использовать, это equals () метод.
Он проверяет, равны ли два объекта. Мы также можем использовать hashCode () вместе с equals () для хеширования ключей без упорядочивания.
// string class must implement equals() method ST<String, Integer> st = new ST<String, Integer>();
Все объекты в Java по умолчанию наследуют методы equals () и hashCode ().
- Неизменяемый
Лучше всего использовать неизменяемые типы для ключей. Почему? Для изменения ключа требуется удалить всю пару "ключ-значение" и снова вставить новый ключ с его значением. Так что мы можем гарантировать, что таблица символов будет согласованной.
Неупорядоченная реализация - использование связанного списка
Начнем с класса таблицы символов. Он имеет ссылочную переменную под названием «первая», указывающая на последний вставленный узел, и целое число N, которое представляет количество элементов в массиве.
public class UnorderedST<Key, Value> {
private Node first = null;
private int N = 0;
}
Затем у нас есть внутренний класс под названием «Узел» для представления каждого узла в таблице символов. У каждого узла есть ключ, значение и ссылка на следующий узел.
private class Node {
private Key key;
private Value val;
private Node next;
public Node(Key key, Value val, Node next) {
this.key = key;
this.val = val;
this.next = next;
}
}
- получить
Сканируем все ключи, пока не найдем совпадение; последовательный поиск. Ключи используют метод equals () для проверки равенства при последовательном поиске.
public Value get(Key key) {
for (Node x = first; x != null; x = x.next) {
if (key.equals(x.key)) // if key exists, return it's value
return x.val;
}
return null; // if key doesn't exist, return null
}
Помните, что ни один ключ не может быть связан со значением null. Следовательно, метод get () возвращает значение null, если ключ не существует.
С этого момента, во время наших реализаций для таблицы символов, может случиться так, что когда ключ равен нулю, на этом этапе вы можете вызвать исключение.
- положить
Сканируйте все ключи, пока не найдем совпадение, и, если оно не совпадает, добавьте в начало.
public void put(Key key, Value val) {
if (val == null) { // remove key from table if value is null
delete(key);
return;
}
// if key exists, overrides the old value (avoid duplicates)
for (Node x = first; x != null; x = x.next) {
if (key.equals(x.key)) {
x.val = val;
return;
}
}
// if key doesn't exist, insert it at the beginning of the list
first = new Node(key, val, first);
N++;
}
- Удалить
Сканируйте все ключи, пока мы не найдем совпадение, и, если оно есть, удалите ключ и связанное с ним значение из списка. Это делается рекурсивно.
public void delete(Key key) {
first = delete(first, key);
}
// A helper method to delete a key in the list given a starting Node
private Node delete(Node current, Key key) {
if (current == null) return null;
if (key.equals(current.key)) {
N--;
return current.next;
}
current.next = delete(current.next, key);
return current;
}
- содержит
Как мы уже упоминали ранее в разделе «Соглашения о таблицах символов». Значения не могут быть нулевыми, и поэтому мы можем проверить, существует ли ключ или нет, проверив, возвращает ли get значение null.
public boolean contains(Key key) { return get(key) != null; }
- Таблица символов пуста?
public boolean isEmpty() { return N == 0; }
Неупорядоченная реализация - использование массива
Вместо использования связного списка для неупорядоченной реализации мы можем использовать массивы.
Начнем с класса таблицы символов. Он имеет два массива: один для хранения ключей (отсортированных) и один для связанных значений, а также целое число N, которое представляет количество элементов в массиве.
public class UnorderedST<Key, Value> {
private Key[] keys;
private Value[] vals;
private int N = 0;
public UnorderedST(int capacity) {
keys = (Key[]) new Object[capacity];
vals = (Value[]) new Object[capacity];
}
}
Нам нужно передать размер массива. Это нарушает идею таблицы символов, которая гласит, что она должна иметь возможность увеличиваться и уменьшаться при любом размере. Но пока будем проще (так же, как мы делали со стеками и очередями).
Java не позволяет создавать универсальные массивы. Итак, нам нужно заняться кастингом.
- Осуществление операций
// get the value associated with the given key.
public Value get(Key key) {
for (int i = 0; i < N; i++)
if (keys[i].equals(key))
return vals[i];
return null;
}
// insert the key-value pair
public void put(Key key, Value val) {
if (val == null) { // remove key from table if value is null
delete(key);
return;
}
// if key exists, overrides the old value (avoid duplicates)
for (int i = 0; i < N; i++) {
if (key.equals(keys[i])) {
vals[i] = val;
return;
}
}
// add new key and value at the end of array
vals[N] = val;
keys[N] = key;
N++;
}
// remove given key and associated value
public void delete(Key key) {
for (int i = 0; i < N; i++) {
// if key exists, swap the key-value pair with the last elem
if (key.equals(keys[i])) {
keys[i] = keys[N-1];
vals[i] = vals[N-1];
keys[N-1] = null; // to avoid loitering
vals[N-1] = null;
N--;
return;
}
}
}
// Is the given key exists?
public boolean contains(Key key) { return get(key) != null; }
// Is the table empty?
public boolean isEmpty() { return N == 0; }
Упорядоченная реализация - использование массива
Как обычно, мы начнем с класса таблицы символов. Он имеет два массива: один для хранения ключей (отсортированных) и один для связанных значений, а также целое число N, которое представляет количество элементов в массиве.
public class OrderedST<Key extends Comparable<Key>, Value> {
private Key[] keys;
private Value[] vals;
private int N = 0;
public OrderedST(int capacity) {
keys = (Key[]) new Comparable[capacity];
vals = (Value[]) new Object[capacity];
}
}
- классифицировать
Вспомогательный метод для получения количества ключей, меньших, чем переданный ключ. Другими словами, он возвращает индекс данного ключа в отсортированном массиве. Он использует алгоритм двоичного поиска по отсортированному массиву.
Затем при поиске, вставке и удалении будет использоваться метод rank ().
public int rank(Key key) {
int lo = 0, hi = N-1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int cmp = key.compareTo(keys[mid]);
if (cmp < 0) hi = mid - 1;
else if (cmp > 0) lo = mid + 1;
else return mid;
}
return lo;
}
Двоичный поиск в упорядоченном массиве с N ключами использует не более logN + 1 сравнений для поиска (успешного или неудачного) в худшем случае.
- получить
Получите индекс ключа в отсортированном массиве keys [] с помощью метода rank (), если он не найден, верните null.
// get the value associated with the given key.
public Value get(Key key) {
int i = rank(key);
if (i < N && keys[i].compareTo(key) == 0)
return vals[i];
return null;
}
- толкать
Получите индекс ключа в отсортированном массиве keys [] с помощью метода rank (), а затем используйте этот индекс для вставки пары "ключ-значение". Когда пришло время вставить, нам нужно сдвинуть все элементы вправо.
// inserts a key-value pair
public void put(Key key, Value val) {
if (val == null) { // remove key from table if value is null
delete(key);
return;
}
// get the rank of the passed key
int i = rank(key);
// if key exists, overrides the old value (avoid duplicates)
if (i < N && keys[i].compareTo(key) == 0) {
vals[i] = val;
return;
}
// shift all elements to right
for (int j = N; j > i; j--) {
keys[j] = keys[j-1];
vals[j] = vals[j-1];
}
// insert the key-value pair in their sorted position
keys[i] = key;
vals[i] = val;
N++;
}
- Удалить
Получите индекс ключа в отсортированном массиве keys [] с помощью метода rank (), а затем используйте этот индекс для удаления пары "ключ-значение". Когда пришло время удалять, нам нужно сдвинуть все элементы влево.
// remove the given key-value pair
public void delete(Key key) {
// get the rank
int i = rank(key);
// key not in table? do nothing.
if (i == N || keys[i].compareTo(key) != 0) {
return;
}
// shift all elements to the left
for (int j = i; j < N-1; j++) {
keys[j] = keys[j+1];
vals[j] = vals[j+1];
}
// the last element now is to be deleted
N--;
keys[N] = null; // to avoid loitering
vals[N] = null;
}
- содержит
// Is the given key exists?
public boolean contains(Key key) { return get(key) != null; }
- Таблица символов пуста?
// Is the table empty?
public boolean isEmpty() { return N == 0; }
Реализация - использование массивов изменения размера
Кроме того, мы можем реализовать таблицу символов, используя массив изменения размера. Таким образом, мы сможем увеличиваться и уменьшаться в любом размере.
Анализ - неупорядоченный против упорядоченного
- Неупорядоченный: get равен O (N) в худшем случае и O (N / 2) ~ O (N) в среднем случае, а положено и delete - O (N) в худшем и среднем случае.
- Упорядочено: get равно O (LogN) в худшем и среднем случае, put и delete равно O (LogN + N) ~ O (N) в худшем случае и O (LogN + N / 2) ~ O (N) в среднем случае.
Операции вставки и удаления из упорядоченного массива занимают время, пропорциональное O (N), из-за смещения элементов вправо и влево.
Если вы используете массив изменения размера, он добавляет дополнительную стоимость постоянного времени (амортизируется) для операций вставки и удаления из неупорядоченного или упорядоченного массива.
Наша цель - найти эффективную реализацию операций; искать, вставлять и удалять.
Суть в том, что упорядоченная реализация является хорошей реализацией для таблиц символов, где пары ключ-значение не сильно меняются; несколько вставок и удалений, и большинство операций - это поиск.
С другой стороны, в динамической ситуации, когда есть много вставок, эта реализация будет проблематичной, потому что стоимость ее вставки в худшем случае линейна.
Заказанные операции
Есть дополнительные полезные операции, которые мы можем предоставить в нашей реализации таблицы символов. Эти операции используют ключевой естественный порядок.
Используя упорядоченную реализацию таблиц символов, где ключи сопоставимы, мы можем поддерживать дополнительные операции, такие как: min, max, floor, потолок, рейтинг, select и т. д.
И для поддержки этих операций для неупорядоченной реализации таблицы символов ключи должны быть сопоставимы. Но это не будет эффективно, поскольку неупорядоченная реализация этих операций (как показано ниже) будет отличаться от реализации упорядоченной таблицы символов.
Условные обозначения операций
Когда метод должен вернуть ключ, а действительный ключ не может быть возвращен, наше соглашение состоит в том, чтобы генерировать исключение (альтернативный подход, который также является разумным, заключался бы в возврате null в таких случаях).
Например, min, max, floor и потолок все выдают исключения, если таблица пуста, как и выберите, если k меньше 0 или не меньше размера массива.
- Мин. и Макс.
Получите самые маленькие и самые большие ключи в наборе ключей.
// get the smallest key
public Key min() {
if (isEmpty()) throw new NoSuchElementException("...");
return keys[0];
}
// get the largest key
public Key max() {
if (isEmpty()) throw new NoSuchElementException("...");
return keys[N-1];
}
- Пол и потолок
Пол - это самый большой ключ, меньший или равный заданному ключу, а потолок - самый маленький ключ, больший или равный заданному ключу.
public Key floor(Key key) {
if (isEmpty()) throw new NoSuchElementException("...");
int i = rank(key);
if (i < N && key.compareTo(keys[i]) == 0)
return keys[i];
if (i == 0) return null;
else return keys[i-1];
}
public Key ceiling(Key key) {
if (isEmpty()) throw new NoSuchElementException("...");
int i = rank(key);
if (i == N) return null;
else return keys[i];
}
- Ранг и выбор
Основные операции по определению, где и какой ключ уместится в отсортированном массиве. rank находит индекс ключа в отсортированном массиве, а select находит ключ с заданным рангом (по заданному индексу в отсортированном массиве).
public int rank(Key key) { /* as before */ }
// return the key at a given rank k; return kth smallest key
public Key select(int k) {
if (k < 0 || k >= N) { // same as when the key is null
throw new IllegalArgumentException("...");
}
return keys[k];
}
- Запросы диапазона
Сколько ключей попадает в заданный диапазон? Какие ключи попадают в заданный диапазон? Два метода; size () и keys () отвечают на эти вопросы.
public int size(Key lo, Key hi) {
if (lo.compareTo(hi) > 0) return 0;
if (contains(hi)) return rank(hi) - rank(lo) + 1;
else return rank(hi) - rank(lo);
}
public Iterable<Key> keys(Key lo, Key hi) {
// create an Iterable object
Queue<Key> queue = new Queue<Key>();
// fill the Iterable object(queue) with the keys
if (lo.compareTo(hi) > 0) return queue;
for (int i = rank(lo); i < rank(hi); i++)
queue.enqueue(keys[i]);
if (contains(hi)) queue.enqueue(keys[rank(hi)]);
// return the Iterable object so we can iterate over the keys
return queue;
}
// if no given range is specified, then iterate over all the keys
public Iterable<Key> keys() { return keys(min(), max()); }
В неупорядоченной реализации таблиц символов ключи расположены не по порядку, поэтому для получения упорядоченной итерации нам нужно сначала выполнить сортировку. В упорядоченном исполнении ключи уже отсортированы.
Анализ - неупорядоченный против упорядоченного
Помните, что в упорядоченной реализации операции вставки и удаления занимают время O (LogN + N / 2) ~ O (N) в среднем случае.
Таблица символов на практике
Найдите количество вхождений каждой строки в последовательности строк, затем перебирает ключи, чтобы найти тот, который встречается наиболее часто
String[] stream = { /*...*/ };
ST<String, Integer> st = new ST<String, Integer>();
for(int i = 0; i < N; i++){
String key = stream[i];
if (st.contains(key))
st.put(key, st.get(key) + 1);
else
st.put(key, 1);
}
// find a key with the highest frequency count
String max = "";
st.put(max, 0);
for (String word : st.keys()) {
if (st.get(word) > st.get(max))
max = word;
}
// CAUTION: get() will return null if st is empty
print(max + " " + st.get(max));
Это приложение не будет работать при большом количестве вводимых данных, если мы не используем эффективную реализацию для операций; put, get и contains.
Вот почему нам необходимо изучить бинарные деревья поиска и хеш-таблицы; структуры данных, которые можно использовать для реализации таблиц символов.
