Shulou(Shulou.com)06/03 Report--

This article introduces the knowledge of "how to implement Map based on array or linked list". Many people will encounter this dilemma in the operation of actual cases, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Preface

Map in JAVA is mainly about associating a key with a value. Although many implementations of Map have been provided in JAVA, in order to learn and master the commonly used data structures, I will implement the function of Map from this article, mainly through array and linked list, and then provide binary tree, red-black tree, hash table version. Through their own handwritten versions of Map implementation, grasp the advantages and disadvantages of each data structure, you can choose the appropriate Map according to the needs in the actual work.

Definition of Map API

Before we start, we need to define the interface definition of Map, which will be implemented in subsequent versions.

Public interface Map {void put (K key, V value); V get (K key); void delete (K key); int size (); Iterable keys (); default boolean contains (K key) {return get (key)! = null;} default boolean isEmpty () {return size () = = 0;}}

This interface is the simplest Map definition, and I believe these methods are no stranger to java programmers.

Implementation of Map based on linked list

First of all, we need to define a Node node that represents the key and vlaue that we need to store.

Class Node {K key; V value; Node next; public Node (K key, V value, Node next) {this.key = key; this.value = value; this.next = next;}}

The implementation idea of the get method is to traverse the linked list, then compare whether the key in each Node is equal, if equal, return value, otherwise return null

@ Override public V get (K key) {return searchNode (key) .map (node-> node.value) .orElse (null);} public Optional searchNode (K key) {for (Node node = root; node! = null; node = node.next) {if (node.key.equals (key)) {return Optional.of (node);}} return Optional.empty ();}

The implementation idea of the put method is also to traverse the linked list, and then compare whether the key values of each Node are equal. If so, overwrite the value. If no node with key equality is found, then create a new Node and put it at the beginning of the linked list.

Override public void put (K key, V value) {Optional optionalNode = searchNode (key); if (optionalNode.isPresent ()) {optionalNode.get (). Value = value; return;} this.root = new Node (key, value, root);}

The implementation of the delete method also needs to traverse the linked list, because we have an one-way linked list. There are two ways to delete a node. The first is to record the previous node of the current node when traversing the linked list, and point the next of the previous node to the current node next. Second, when traversing to the node that needs to be deleted, copy the key and value of the next of the node to be deleted completely to the node that needs to be deleted, and point the next pointer to the next.next, such as: first-> A-> B-> C-> D-> E-> F-> G-> NULL. To delete the C node, copy the D node completely into c, and then C-> E, delete C in disguise.

@ Override public void delete (K key) {/ / first implementation: / / for (Node node = first, preNode = null; node! = null; preNode = node, node = node.next) {/ / if (node.key.equals (key)) {/ / if (Objects.isNull (preNode)) {/ / first = first.next / /} else {/ / preNode.next = node.next; / /} / / second implementation: for (Node node = first; node! = null; node = node.next) {if (node.key.equals (key)) {Node next = node.next Node.key = next.key; node.value = next.value; node.next = next.next;}

Analysis of the above map based on linked list, each put, get, delete need to traverse the entire linked list, very inefficient, unable to deal with a large amount of data, the time complexity is O (N).

"

Implementation of Map based on array

The implementation based on linked list is very inefficient, because every operation needs to traverse the linked list, if our data is orderly, then we can use binary search method when searching, then get method will be much faster.

In order to show that our Map is orderly, we need to redefine an ordered Map

Public interface SortedMap extends Map {int rank (K key);}

This definition requires that key must implement the interface Comparable,rank method to return the corresponding subscript in the array if the key value exists, and the number of keys less than key if it does not exist.

In the array-based implementation, we will define two array variables to store keys and values in parts

Implementation of the rank method: since our entire array is ordered, we can split the search method (see "it's time for my brother to review the data structure and algorithm"), return the following table of the array if it exists, and return 0 if it doesn't exist.

@ Override public int rank (K key) {int lo = 0, hi = size-1; while (lo 0) {lo = mid + 1;} else if (compare

< 0) { hi = mid - 1; } else { return mid; } } return lo; } get方法实现：基于rank方法，判断返回的keys[index]与key进行比较，如果相等返回values[index]，不相等就返回null @Override public V get(K key) { int index = this.rank(key); if (index < size && key.compareTo(keys[index]) == 0) { return values[index]; } return null; } put方法实现：基于rank方法，判断返回的keys[index]与key进行比较，如果相等直接修改values[index]的值，如果不相等表示不存在该key，需要插入并且移动数组 @Override public void put(K key, V value) { int index = this.rank(key); if (index < size && key.compareTo(keys[index]) == 0) { values[index] = value; return; } for (int j = size; j >

Index; Jmuri -) {this.keys [j] = this.keys [JMY -]; this.values [j] = this.values [Jmuri -];} keys [index] = key; values [index] = value; size++;}

Delete method implementation: use the rank method to determine whether the key exists, return it directly if it does not exist, and move the array if it exists

@ Override public void delete (K key) {int index = this.rank (key); if (Objects.isNull) | | key.compareTo (Keys [index])! = 0) {return;} for (int j = index; j < size-1; jacks +) {keys [j] = keys [j + 1]; values [j] = values [j + 1];} keys [size-1] = null Values [size- 1] = null; size--;}

Map based on array, although the binary search method used by get method is very fast O (logN), the efficiency is still very low when dealing with a large amount of data, because the put method is still too slow.

This is the end of the tutorial on how to implement Map based on arrays or linked lists. Thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.