Created
June 20, 2018 17:26
-
-
Save DonKeyHot1/e2570be831258babd4532806feee2603 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public interface IDictionary { | |
/** | |
* Помещает значение в ячейку с указанным ключем | |
* @param key - ключ | |
* @param value - значение | |
* @return true - если помещение успешно, иначе - false | |
*/ | |
boolean put(String key, String value); | |
/** | |
* @param key - ключ | |
* @return значение ассоциированное с указанным ключем | |
*/ | |
String get(String key); | |
/** | |
* Удаляет из структуры значение с указанным ключем | |
* @param key - ключ | |
* @return true - если удаление успешно, иначе - false | |
*/ | |
boolean remove(String key); | |
/** | |
* Проверяет структуру на пустоту | |
* @return true - если в структуре нет значений, иначе false | |
*/ | |
boolean isEmpty(); | |
} | |
import java.util.HashMap; | |
import java.util.Map; | |
public class Dictionary implements IDictionary { | |
private Node root = new Node(); | |
private static class Node { | |
Map<Character, Node> children = new HashMap<>(); | |
Node parent = null; | |
String value = null; | |
} | |
@Override | |
public boolean put(String key, String value) { | |
try { | |
Node currentNode = root; | |
Node currentParent; | |
for(char character : key.toCharArray()) { | |
if (!currentNode.children.containsKey(character)) { | |
currentNode.children.put(character, new Node()); | |
} | |
currentParent = currentNode; | |
currentNode = currentNode.children.get(character); | |
currentNode.parent = currentParent; | |
} | |
currentNode.value = value; | |
return true; | |
} catch (Exception e) { | |
System.out.println("Добавление не удалось. Причина: " + e.getMessage()); | |
return false; | |
} | |
} | |
@Override | |
public String get(String key) { | |
Node currentNode = root; | |
for (char character : key.toCharArray()) { | |
if (!currentNode.children.containsKey(character)) { | |
return null; | |
} else { | |
currentNode = currentNode.children.get(character); | |
} | |
} | |
return currentNode.value; | |
} | |
@Override | |
public boolean remove(String key) { | |
try { | |
Node currentNode = root; | |
for (char character : key.toCharArray()) { | |
if (!currentNode.children.containsKey(character)) { | |
return false; | |
} else { | |
currentNode = currentNode.children.get(character); | |
} | |
} | |
currentNode.value = null; | |
while (currentNode.parent != null && currentNode.children.size() == 0) { | |
Node currentParent = currentNode.parent; | |
if (currentParent.children.size() == 1 && currentNode.value == null) { | |
currentParent.children.clear(); | |
currentNode = currentParent; | |
} | |
else { | |
break; | |
} | |
} | |
return true; | |
} catch (Exception e) { | |
System.out.println("Удаление не удалось. Причина: " + e.getMessage()); | |
return false; | |
} | |
} | |
@Override | |
public boolean isEmpty() { | |
return root.children.isEmpty(); | |
} | |
} | |
import java.util.ArrayList; | |
import java.util.HashMap; | |
import java.util.List; | |
import java.util.Random; | |
public class Main { | |
private static final int NUMBER_OF_ELEMENTS = 1000000; | |
public static void main(String[] args) { | |
Dictionary dictionary = new Dictionary(); | |
HashMap<String, String> map = new HashMap<>(); | |
List<String> keys = new ArrayList<>(); | |
List<String> values = new ArrayList<>(); | |
for (int i = 0; i < NUMBER_OF_ELEMENTS; i++) { | |
keys.add(getRandomString(10)); | |
values.add(getRandomString(50)); | |
} | |
long start = System.currentTimeMillis(); | |
for (int i = 0; i < keys.size(); i++) { | |
dictionary.put(keys.get(i), values.get(i)); | |
} | |
long end = System.currentTimeMillis(); | |
System.out.println("Время добавления в Dictionary: " + (end - start) + " мсекунд."); | |
start = System.currentTimeMillis(); | |
for (int i = 0; i < keys.size(); i++) { | |
map.put(keys.get(i), values.get(i)); | |
} | |
end = System.currentTimeMillis(); | |
System.out.println("Время добавления в HashMap: " + (end - start) + " мсекунд."); | |
start = System.currentTimeMillis(); | |
for (int i = 0; i < keys.size(); i++) { | |
dictionary.get(keys.get(i)); | |
} | |
end = System.currentTimeMillis(); | |
System.out.println("Время взятия элемента в Dictionary: " + (end - start) + " мсекунд."); | |
start = System.currentTimeMillis(); | |
for (int i = 0; i < keys.size(); i++) { | |
map.get(keys.get(i)); | |
} | |
end = System.currentTimeMillis(); | |
System.out.println("Время взятия элемента в HashMap: " + (end - start) + " мсекунд."); | |
start = System.currentTimeMillis(); | |
for (int i = 0; i < keys.size(); i++) { | |
dictionary.remove(keys.get(i)); | |
} | |
end = System.currentTimeMillis(); | |
System.out.println("Время удаления элемента в Dictionary: " + (end - start) + " мсекунд."); | |
start = System.currentTimeMillis(); | |
for (int i = 0; i < keys.size(); i++) { | |
map.remove(keys.get(i)); | |
} | |
end = System.currentTimeMillis(); | |
System.out.println("Время удаления элемента в HashMap: " + (end - start) + " мсекунд."); | |
} | |
private static String getRandomString(int length) { | |
String chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890"; | |
StringBuilder sb = new StringBuilder(); | |
Random rnd = new Random(); | |
while(sb.length() < length) | |
{ | |
int index = (int) (rnd.nextFloat() * chars.length()); | |
sb.append(chars.charAt(index)); | |
} | |
return sb.toString(); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment