When inserting the first 8 pairs of keys and values it works perfectly fine and the order is maintained, the problem comes after the resizing. If I insert the pairs (4,4),(5,5),(6,6),(7,7),(1,1),(2,2),(3,3) the order is maintained and the dict looks like this [(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7)] but if I insert (8,8) the resize comes in action and then the insertion order is completely changed because the doubly linked list still has the first insertions (4,4)(5,5)(6,6)(7,7)(1,1)(2,2)(3,3) and now adds to the tail one by one the elements in the dict so the Doubly linked list ends up like this: (4,4),(5,5),(6,6),(7,7),(1,1),(2,2),(3,3),(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7). Here´s my doubly linked list class:
public class DoubleLinkedList {
Node<K, V> head;
Node<K, V> tail;
public DoubleLinkedList() {
head = null;
tail = null;
}
public void insertAtEnd(Node<K, V> node)
{
if (tail == null) {
head = node;
tail = node;
}
else {
tail.next = node;
node.prev = tail;
tail = node;
}
}
}
Here is my Dict class and Node class:
public class Dict<K, V> implements Iterable<K>{
public static class Node<K, V> {
private K key;
private V value;
// liberado == 1, ocupado == 0
private int state;
private Node<K, V> next;
private Node<K, V> prev;
}
private Node<K, V>[] dict;
private int size;
private final double loadFactor = 0.80;
private DoubleLinkedList list;
public Dict() {
this.size = 0;
this.dict = new Node[10];
this.list = new DoubleLinkedList();
}
And here are my resize and put methods:
public void put(K key, V value) {
if (this.size + 1 > (this.dict.length * 0.8)) {
resize();
}
int clave = disperse(key);
for (int i = 0; i <= dict.length; i++) {
int index = (clave + i) % this.dict.length;
if (dict[index] == null || dict[index].getState() == 1) {
Node<K, V> newNode = new Node(key, value);
dict[index] = newNode;
list.insertAtEnd(newNode);
this.size++;
return;
} else if (dict[index] != null && dict[index].key.equals(key)) {
dict[index].value = value;
System.out.println(dict[index].value);
return;
}
}
}
private void resize() {
int capacidad = (int) (dict.length * 1.5);
Node<K, V>[] antiguoDict = this.dict;
this.dict = new Node[capacidad];
size = 0;
for(Node<K, V> node : antiguoDict){
if(node != null){
put(node.key, node.value);
}
}
}
I was trying this solution:
private void resize() {
int capacidad = (int) (dict.length * 1.5);
int prev_size = size;
Node<K, V>[] nuevoDict= new Node[capacidad];
Node<K, V> current = this.list.head;
this.dict = nuevoDict;
for (int i = 0; i < prev_size; i++) {
put(current.key, current.value);
pop(current.getKey());
current = this.list.head;
}
}
Where I use this pop method:
public void pop(K key) throws NullPointerException {
int clave = disperse(key);
for (int i = 0; i < dict.length; i++) {
int index = (clave + i) % this.dict.length;
Node<K, V> node = dict[index];
if (node == null) {
throw new NullPointerException();
}
if (node.key.equals(key)) {
if (node.prev != null) {
node.prev.next = node.next;
} else {
list.head = node.next;
}
if (node.next != null) {
node.next.prev = node.prev;
} else {
list.tail = node.prev;
}
dict[index] = new Node<>(null, null, 1);
size--;
return;
}
}
throw new NullPointerException();
}
But the pop method just eliminates the value I have just put inside the dict and so the dict is empty.
When inserting the first 8 pairs of keys and values it works perfectly fine and the order is maintained, the problem comes after the resizing. If I insert the pairs (4,4),(5,5),(6,6),(7,7),(1,1),(2,2),(3,3) the order is maintained and the dict looks like this [(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7)] but if I insert (8,8) the resize comes in action and then the insertion order is completely changed because the doubly linked list still has the first insertions (4,4)(5,5)(6,6)(7,7)(1,1)(2,2)(3,3) and now adds to the tail one by one the elements in the dict so the Doubly linked list ends up like this: (4,4),(5,5),(6,6),(7,7),(1,1),(2,2),(3,3),(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7). Here´s my doubly linked list class:
public class DoubleLinkedList {
Node<K, V> head;
Node<K, V> tail;
public DoubleLinkedList() {
head = null;
tail = null;
}
public void insertAtEnd(Node<K, V> node)
{
if (tail == null) {
head = node;
tail = node;
}
else {
tail.next = node;
node.prev = tail;
tail = node;
}
}
}
Here is my Dict class and Node class:
public class Dict<K, V> implements Iterable<K>{
public static class Node<K, V> {
private K key;
private V value;
// liberado == 1, ocupado == 0
private int state;
private Node<K, V> next;
private Node<K, V> prev;
}
private Node<K, V>[] dict;
private int size;
private final double loadFactor = 0.80;
private DoubleLinkedList list;
public Dict() {
this.size = 0;
this.dict = new Node[10];
this.list = new DoubleLinkedList();
}
And here are my resize and put methods:
public void put(K key, V value) {
if (this.size + 1 > (this.dict.length * 0.8)) {
resize();
}
int clave = disperse(key);
for (int i = 0; i <= dict.length; i++) {
int index = (clave + i) % this.dict.length;
if (dict[index] == null || dict[index].getState() == 1) {
Node<K, V> newNode = new Node(key, value);
dict[index] = newNode;
list.insertAtEnd(newNode);
this.size++;
return;
} else if (dict[index] != null && dict[index].key.equals(key)) {
dict[index].value = value;
System.out.println(dict[index].value);
return;
}
}
}
private void resize() {
int capacidad = (int) (dict.length * 1.5);
Node<K, V>[] antiguoDict = this.dict;
this.dict = new Node[capacidad];
size = 0;
for(Node<K, V> node : antiguoDict){
if(node != null){
put(node.key, node.value);
}
}
}
I was trying this solution:
private void resize() {
int capacidad = (int) (dict.length * 1.5);
int prev_size = size;
Node<K, V>[] nuevoDict= new Node[capacidad];
Node<K, V> current = this.list.head;
this.dict = nuevoDict;
for (int i = 0; i < prev_size; i++) {
put(current.key, current.value);
pop(current.getKey());
current = this.list.head;
}
}
Where I use this pop method:
public void pop(K key) throws NullPointerException {
int clave = disperse(key);
for (int i = 0; i < dict.length; i++) {
int index = (clave + i) % this.dict.length;
Node<K, V> node = dict[index];
if (node == null) {
throw new NullPointerException();
}
if (node.key.equals(key)) {
if (node.prev != null) {
node.prev.next = node.next;
} else {
list.head = node.next;
}
if (node.next != null) {
node.next.prev = node.prev;
} else {
list.tail = node.prev;
}
dict[index] = new Node<>(null, null, 1);
size--;
return;
}
}
throw new NullPointerException();
}
But the pop method just eliminates the value I have just put inside the dict and so the dict is empty.
Share Improve this question asked Mar 22 at 16:29 GoldenPlus 89GoldenPlus 89 111 bronze badge1 Answer
Reset to default 0Your resize() method calls the put() method to copy the nodes from the old dictionary to the new one. That means that the linked list nodes get duplicated by this line in the put() method:
list.insertAtEnd(newNode);
I think you should avoid calling put() when copying nodes to the new dictionary so that the existing nodes are not re-added to the linked list.
发布者：admin，转转请注明出处：http://www.yc00.com/questions/1744308638a4567841.html
评论列表（0条）