数据结构之Hash

数据结构之hash
首先介绍两种非常重要的数据结构。数组，为了方便我们把同类型的数据按照一定的数据放在一起[][][][]，数组的好处在于，数组的查找很方便，只要知道下标便可以找到数据，但是数据的大小超过数组的大小时，那么就会变得非常麻烦，在java等强类型语言中数组的大小一旦被定义那么就无法改变（javascript中如果定义了一个10长度的数组a可以直接扩张该数组，比如a[10]），我们就只能创建一个新的数组，然后将原数组中的内容拿出来重新放到新数组中。这样做是很麻烦的。还有另外一种数据结构，链表，链表就像一根环环相扣的链子。链表的连接类似于如下结构，每个节点指向它的下一个节点O->O->O->... 对于链表来说添加添加数据很方便，但是，但你要查找一个数据是每次要重第一个节点开始遍历，这样查找或者修改是很麻烦的。
结合了数组和链表的优点，出现了一种新的数据结构--Hash,Hash结构在确保了查找速度的同时，确保了可以方便的添加节点。
         [O]  [O]  [O]  [O]  [O]  [O]  [O]
          ↓      ↓      ↓     ↓      ↓     ↓      ↓
          O     O    O     O    O     O     O
          ↓      ↓     ↓      ↓     ↓      ↓       ↓
          O     O    O     O    O     O     O
          ↓      ↓      ↓     ↓     ↓      ↓       ↓
          .      .      .      .      .       .        .
          .      .      .      .      .       .        .
          .      .      .      .      .       .        .

我们可以先使用java中的HashSet接口，当我们向HashSet中存入一个元素时，HashSet会调用该对象的hashCode()方法来得到该对象的hashCode值，根据该值确定该对象在HashSet中的位置。也就是说每个对象的hashCode值就是他的所以。

    String a1 = new String("aaa");
        String a2 = new String("aaa");
        String a3 = new String("aaa");
        System.out.println("a1:"+a1.hashCode()+" a2:"+a2.hashCode()+" a3:"+a3.hashCode());
Output：a1:96321 a2:96321 a3:96321

 

我们把数据放在很多个链表里面，把根数据放在数组里面。每个数据节点有一个key值，我们通过key值计算出其应该在的数组中下标index(使用key对数组的长度取模)，若是该数组没有数据，那么就让下标为index的等于该节点，若是index上已经有了数据，那么我们就让该数据成为该链的一个节点。同时我们在加入节点的同时还要记录已加入的节点数，并计算阀值，判断是否应该增大数组的大小，重新分配

    public void addNode(HashNode newNode) {
        int index = getIndex(newNode);//
        if (hashArray[index] == null) {
            hashArray[index] = newNode;
            newNode.setNext(null);
        } else {
            HashNode node = hashArray[index];
            newNode.setNext(node.getNext());
            node.setNext(newNode);
        }
        length++;
    }

 

根据节点的key值计算出该节点在数组中应该存在的位置,对key之和数组的大小取模，
    public int getIndex(HashNode node) {
        return node.getKey() % arraySize;
    }
我们不能让数组的hash表中的数据不断增加当数据的个数是数组长度的阀值倍是我们扩充数组的长度，同时重新分配所有节点的位置

 if ((length / arraySize) >= load) {
            refresh();
        }

 

 

 // 当hash数组的长度改变时更新hash表
        public void refresh() {
            printHash();
            HashNode[] newHashArray = new HashNode[arraySize * 2];// 创建心新的数组
            arraySize = arraySize * 2;
            for (int i = 0; i < hashArray.length; i++) {
                    HashNode node = hashArray[i];
                while (node != null) {
                    int index = getIndex(node);
                    System.out.println("refresh-->" + "key:" + node.getKey() + " "
                        + "value:" + node.getValue() + " " + "index: " + index);
                    node = node.getNext();
                    if (newHashArray[index] == null) {
                        newHashArray[index] = node;
                        node.setNext(null);
                    } else {
                        HashNode this_node = newHashArray[index];
                        node.setNext(this_node.getNext());
                        this_node.setNext(node);
                    }
                    System.out.println("node-->next" + node.getKey());
                }
            }
            hashArray = newHashArray;
        }