- Коэффициент загрузки хэш-карты Java
- 2. Что такое HashMap?
- 3. Внутренние компоненты HashMap
- 4. Настраиваемая Начальная емкость и коэффициент нагрузки
- 4.1. С Начальной Мощностью
- 4.2. С Начальной мощностью и коэффициентом нагрузки
- 5. Производительность
- 5.1. Сложность
- 5.2. Пересказ
- 5.3. Столкновение
- 6. Заключение
- Использование Google Map в приложении на JavaFX
- Реализация
- Результат
Коэффициент загрузки хэш-карты Java
В этой статье мы рассмотрим значение коэффициента загрузки в Java HashMap и то, как он влияет на производительность карты.
2. Что такое HashMap?
Класс HashMap принадлежит к структуре коллекции Java и обеспечивает базовую реализацию интерфейса Map . Мы можем использовать его, когда хотим хранить данные в терминах пар ключ-значение. Эти пары ключ-значение называются записями карты и представлены классом Map.Entry .
3. Внутренние компоненты HashMap
Прежде чем обсуждать коэффициент нагрузки, давайте рассмотрим несколько терминов:
-
- хеширование
- вместимость
- порог
- перефразирование
- столкновение
HashMap работает по принципу хеширования — алгоритма сопоставления данных объекта с некоторым репрезентативным целочисленным значением . Функция хэширования применяется к ключевому объекту для вычисления индекса корзины для хранения и извлечения любой пары ключ-значение.
Емкость-это количество ведер в HashMap . Начальная емкость-это емкость на момент создания M ap . Наконец, начальная емкость HashMap по умолчанию равна 16.
По мере увеличения количества элементов в HashMap емкость расширяется. Коэффициент нагрузки-это мера, которая решает, когда следует увеличить пропускную способность Карты . Коэффициент загрузки по умолчанию составляет 75% от емкости.
Пороговое значение HashMap приблизительно равно произведению текущей емкости и коэффициента нагрузки. Повторное хэширование – это процесс пересчета хэш-кода уже сохраненных записей. Проще говоря, когда количество записей в хэш-таблице превышает пороговое значение, Map перефразируется так, чтобы в нем было примерно в два раза больше ведер, чем раньше.
Коллизия возникает, когда хэш-функция возвращает одно и то же местоположение корзины для двух разных ключей.
Давайте создадим нашу HashMap :
Map
Вот структура нашей карты :
Как мы видим, наша HashMap была создана с начальной емкостью по умолчанию (16) и коэффициентом загрузки по умолчанию (0,75). Кроме того, пороговое значение равно 16 *, что означает, что оно увеличит емкость с 16 до 32 после добавления 12-й записи (пары ключ-значение).
4. Настраиваемая Начальная емкость и коэффициент нагрузки
В предыдущем разделе мы создали нашу HashMap с помощью конструктора по умолчанию. В следующих разделах мы рассмотрим, как создать HashMap , передав конструктору начальную емкость и коэффициент загрузки.
4.1. С Начальной Мощностью
Во-первых, давайте создадим Карту с начальной емкостью:
Map
Он создаст пустую карту с начальной емкостью (5) и коэффициентом загрузки по умолчанию (0,75).
4.2. С Начальной мощностью и коэффициентом нагрузки
Аналогично, мы можем создать нашу карту , используя как начальную емкость, так и коэффициент загрузки:
Map
Здесь он создаст пустую карту с начальной емкостью 5 и коэффициентом загрузки 0,5.
5. Производительность
Хотя у нас есть гибкость в выборе начальной мощности и коэффициента нагрузки, мы должны выбирать их с умом. Оба они влияют на производительность Map . Давайте углубимся в то, как эти параметры связаны с производительностью.
5.1. Сложность
Как мы знаем, HashMap внутренне использует хэш-код в качестве основы для хранения пар ключ-значение. Если метод hashCode() хорошо написан, HashMap распределит элементы по всем корзинам. Поэтому HashMap хранит и извлекает записи в постоянное время O(1) .
Однако проблема возникает, когда количество элементов увеличивается, а размер ведра фиксируется. В каждом ведре будет больше предметов, и это будет мешать временной сложности.
Решение заключается в том, что мы можем увеличить количество ведер, когда количество элементов увеличивается. Затем мы можем перераспределить элементы по всем ведрам. Таким образом, мы сможем сохранить постоянное количество элементов в каждом ведре и поддерживать временную сложность O(1) .
Здесь коэффициент загрузки помогает нам решить, когда следует увеличить количество ведер . При более низком коэффициенте нагрузки будет больше свободных ведер и, следовательно, меньше шансов на столкновение. Это поможет нам добиться лучшей производительности для нашей карты . Следовательно, нам нужно поддерживать низкий коэффициент нагрузки, чтобы достичь низкой временной сложности .
HashMap обычно имеет пространственную сложность O(n) , где n – количество записей. Более высокое значение коэффициента загрузки уменьшает накладные расходы на пространство, но увеличивает стоимость поиска .
5.2. Пересказ
Когда количество элементов в Карте пересекает пороговое значение, емкость Карты удваивается. Как обсуждалось ранее, при увеличении емкости нам необходимо равномерно распределить все записи (включая существующие записи и новые записи) по всем сегментам. Здесь нам нужно перефразировать. То есть для каждой существующей пары ключ-значение снова вычислите хэш-код с увеличенной емкостью в качестве параметра.
В принципе, когда коэффициент нагрузки увеличивается, сложность возрастает. Перефразирование выполняется для поддержания низкого коэффициента нагрузки и низкой сложности всех операций.
Давайте инициализируем нашу Карту :
Map
И давайте взглянем на структуру карты :
Теперь давайте добавим больше записей на нашу Карту :
mapWithInitialCapacityAndLF.put("6", "Six"); mapWithInitialCapacityAndLF.put("7", "Seven"); //.. more entries mapWithInitialCapacityAndLF.put("15", "fifteen");И давайте еще раз понаблюдаем за нашей Картой структурой:
Хотя перефразирование помогает сохранить низкую сложность, это дорогостоящий процесс. Если нам нужно хранить огромное количество данных, мы должны создать нашу HashMap с достаточной емкостью. Это более эффективно, чем автоматическое перефразирование.
5.3. Столкновение
Коллизии могут возникать из-за плохого алгоритма хэш-кода и часто замедляют производительность карты .
До Java 8 HashMap в Java обрабатывает коллизии с помощью LinkedList для хранения записей карты. Если ключ оказывается в том же ведре, где уже существует другая запись, он добавляется в начало связанного списка /. В худшем случае это увеличит сложность до O(n) .
Чтобы избежать этой проблемы, Java 8 и более поздние версии используют сбалансированное дерево (также называемое красно-черным деревом ) вместо LinkedList для хранения конфликтующих записей. Это улучшает наихудшую производительность HashMap от O(n) до O(log n) .
HashMap изначально использует Связанный список. Затем, когда количество записей превысит определенный порог, он заменит LinkedList сбалансированным двоичным деревом. Константа TREEIFY_THRESHOLD определяет это пороговое значение. В настоящее время это значение равно 8, что означает, что если в одном ведре находится более 8 элементов, Map будет использовать дерево для их хранения.
6. Заключение
В этой статье мы обсудили одну из самых популярных структур данных: HashMap . Мы также видели, как фактор нагрузки вместе с емкостью влияет на его производительность.
Как всегда, примеры кода для этой статьи доступны на GitHub .
Использование Google Map в приложении на JavaFX
Хочу рассказать о своем опыте использования Google Maps в приложении на JavaFX. Рассмотрим загрузку карты в приложение и вызов Google Maps JavaScript API v3 для загруженной карты из своего кода на Java.
Реализация
Сначала напишем код инициализации карты на javascript, который оформим ввиде html-страницы map.html. Далее по мере продвижения будем добавлять дополнительный код.
html < height: 100% >body < height: 100%; margin: 0; padding: 0 >#map_canvasТеперь у нас есть html-страница с картой. Ее можно открыть в любом браузере. В JavaFX есть замечательный класс для отображения веб-контента: javafx.scene.web.WebView. Воспользуемся им для отображения написанной html-странички. Напишем класс GoogleMap, который будет представлять Google Map в нашем приложении на JavaFX. Чтобы работать с картой как с любым другим JavaFX-нодом (Scene graph node), унаследуемся от класса javafx.scene.Parent.
public class GoogleMap extends Parent < public GoogleMap() < initMap(); getChildren().add(webView); >private void initMap() < webView = new WebView(); webEngine = webView.getEngine(); webEngine.load(getClass().getResource("map.html").toExternalForm()); ready = false; webEngine.getLoadWorker().stateProperty().addListener(new ChangeListener() < @Override public void changed(final ObservableValueobservableValue, final Worker.State oldState, final Worker.State newState) < if (newState == Worker.State.SUCCEEDED) < ready = true; >> >); > private WebView webView; private WebEngine webEngine; private boolean ready; >Простого отображения карты не достаточно. Нам хочется управлять картой и отлавливать события карты. Для обращения к функциям на javascript нам потребуется экземпляр класса netscape.javascript.JSObject, который получим в методе initCommunication(), вызываемом в конструкторе класса GoogleMap. Так же в этом методе закинем в контекст javascript кода GoogleMap.this (экземпляр класса GoogleMap), чтобы иметь возможность вызывать методы класса GoogleMap из кода на javascript.
private void initCommunication() < webEngine.getLoadWorker().stateProperty().addListener(new ChangeListener() < @Override public void changed(final ObservableValueobservableValue, final Worker.State oldState, final Worker.State newState) < if (newState == Worker.State.SUCCEEDED) < doc = (JSObject) webEngine.executeScript("window"); doc.setMember("app", GoogleMap.this); >> >); > private JSObject doc;Продемонстрируем вызов Java кода из javascript кода на примере отлавливания события клика по карте. Это событие, как ни странно, возникает при нажатии на карту и содержит географические координаты нажатия. Сначала напишем класс события:
public class MapEvent extends Event < public MapEvent(GoogleMap map, double lat, double lng) < super(map, Event.NULL_SOURCE_TARGET, Event.ANY); this.lat = lat; this.lng = lng; >public double getLat() < return this.lat; >public double getLng() < return this.lng; >private double lat; private double lng; >Теперь напишем методы класса GoogleMap, ответственные за регистрацию обработчика, прием события от javasript кода и вызов обработчика:
public void setOnMapLatLngChanged(EventHandler eventHandler) < onMapLatLngChanged = eventHandler; >public void handle(double lat, double lng) < if(onMapLatLngChanged != null) < MapEvent event = new MapEvent(this, lat, lng); onMapLatLngChanged.handle(event); >> private EventHandler onMapLatLngChanged;Осталось только написать обработчик события карты в javascript коде и вызвать в нем метод handle(double lat, double lng) класса GoogleMap:
function get_click_position(event)
private void invokeJS(final String str) < if(ready) < doc.eval(str); >else < webEngine.getLoadWorker().stateProperty().addListener(new ChangeListener() < @Override public void changed(final ObservableValueobservableValue, final Worker.State oldState, final Worker.State newState) < if (newState == Worker.State.SUCCEEDED) < doc.eval(str); >> >); > >Результат
Не буду отдельно пояснять методы установки типа карты, положения центра карты, положения курсора. Все эти методы есть в полных исходниках:
public class GoogleMap extends Parent < public GoogleMap() < initMap(); initCommunication(); getChildren().add(webView); setMarkerPosition(0,0); setMapCenter(0, 0); switchTerrain(); >private void initMap() < webView = new WebView(); webEngine = webView.getEngine(); webEngine.load(getClass().getResource("resources/map.html").toExternalForm()); ready = false; webEngine.getLoadWorker().stateProperty().addListener(new ChangeListener() < @Override public void changed(final ObservableValueobservableValue, final Worker.State oldState, final Worker.State newState) < if (newState == Worker.State.SUCCEEDED) < ready = true; >> >); > private void initCommunication() < webEngine.getLoadWorker().stateProperty().addListener(new ChangeListener() < @Override public void changed(final ObservableValueobservableValue, final Worker.State oldState, final Worker.State newState) < if (newState == Worker.State.SUCCEEDED) < doc = (JSObject) webEngine.executeScript("window"); doc.setMember("app", GoogleMap.this); >> >); > private void invokeJS(final String str) < if(ready) < doc.eval(str); >else < webEngine.getLoadWorker().stateProperty().addListener(new ChangeListener() < @Override public void changed(final ObservableValueobservableValue, final Worker.State oldState, final Worker.State newState) < if (newState == Worker.State.SUCCEEDED) < doc.eval(str); >> >); > > public void setOnMapLatLngChanged(EventHandler eventHandler) < onMapLatLngChanged = eventHandler; >public void handle(double lat, double lng) < if(onMapLatLngChanged != null) < MapEvent event = new MapEvent(this, lat, lng); onMapLatLngChanged.handle(event); >> public void setMarkerPosition(double lat, double lng) < String sLat = Double.toString(lat); String sLng = Double.toString(lng); invokeJS("setMarkerPosition(" + sLat + ", " + sLng + ")"); >public void setMapCenter(double lat, double lng) < String sLat = Double.toString(lat); String sLng = Double.toString(lng); invokeJS("setMapCenter(" + sLat + ", " + sLng + ")"); >public void switchSatellite() < invokeJS("switchSatellite()"); >public void switchRoadmap() < invokeJS("switchRoadmap()"); >public void switchHybrid() < invokeJS("switchHybrid()"); >public void switchTerrain() < invokeJS("switchTerrain()"); >public void startJumping() < invokeJS("startJumping()"); >public void stopJumping() < invokeJS("stopJumping()"); >public void setHeight(double h) < webView.setPrefHeight(h); >public void setWidth(double w) < webView.setPrefWidth(w); >public ReadOnlyDoubleProperty widthProperty() < return webView.widthProperty(); >private JSObject doc; private EventHandler onMapLatLngChanged; private WebView webView; private WebEngine webEngine; private boolean ready; >html < height: 100% >body < height: 100%; margin: 0; padding: 0 >#map_canvasКак сказал Вольтер:
«Я могу быть не согласным с Вашим мнением, но я готов отдать жизнь за Ваше право высказывать его.»
