参见英文答案 >

Why does a HashMap rehash the hashcode supplied by the key object?                                    4个

以下是从简介到Java编程(Liang)的示例：

import java.util.LinkedList;

public class MyHashSet implements MySet {

// Define the default hash table size. Must be a power of 2

private static int DEFAULT_INITIAL_CAPACITY = 16;

// Define the maximum hash table size. 1 << 30 is same as 2^30

private static int MAXIMUM_CAPACITY = 1 << 30;

// Current hash table capacity. Capacity is a power of 2

private int capacity;

// Define default load factor

private static float DEFAULT_MAX_LOAD_FACTOR = 0.75f;

// Specify a load factor threshold used in the hash table

private float loadFactorThreshold;

// The number of entries in the set

private int size = 0;

// Hash table is an array with each cell that is a linked list

private LinkedList[] table;

/** Construct a set with the default capacity and load factor */

public MyHashSet() {

this(DEFAULT_INITIAL_CAPACITY, DEFAULT_MAX_LOAD_FACTOR);

}

/** Construct a set with the specified initial capacity and

* default load factor */

public MyHashSet(int initialCapacity) {

this(initialCapacity, DEFAULT_MAX_LOAD_FACTOR);

}

/** Construct a set with the specified initial capacity

* and load factor */

public MyHashSet(int initialCapacity, float loadFactorThreshold) {

if (initialCapacity > MAXIMUM_CAPACITY)

this.capacity = MAXIMUM_CAPACITY;

else

this.capacity = trimToPowerOf2(initialCapacity);

this.loadFactorThreshold = loadFactorThreshold;

table = new LinkedList[capacity];

}

/** Remove all elements from this set */

public void clear() {

size = 0;

removeElements();

}

/** Return true if the element is in the set */

public boolean contains(E e) {

int bucketIndex = hash(e.hashCode());

if (table[bucketIndex] != null) {

LinkedList bucket = table[bucketIndex];

for (E element: bucket)

if (element.equals(e))

return true;

}

return false;

}

/** Add an element to the set */

public boolean add(E e) {

if (contains(e))

return false;

if (size > capacity * loadFactorThreshold) {

if (capacity == MAXIMUM_CAPACITY)

throw new RuntimeException("Exceeding maximum capacity");

rehash();

}

int bucketIndex = hash(e.hashCode());

// Create a linked list for the bucket if it is not created

if (table[bucketIndex] == null) {

table[bucketIndex] = new LinkedList();

}

// Add e to hashTable[index]

table[bucketIndex].add(e);

size++; // Increase size

return true;

}

/** Remove the element from the set */

public boolean remove(E e) {

if (!contains(e))

return false;

int bucketIndex = hash(e.hashCode());

// Create a linked list for the bucket if it is not created

if (table[bucketIndex] != null) {

LinkedList bucket = table[bucketIndex];

for (E element: bucket)

if (e.equals(element)) {

bucket.remove(element);

break;

}

}

size--; // Decrease size

return true;

}

/** Return true if the set contains no elements */

public boolean isEmpty() {

return size == 0;

}

/** Return the number of elements in the set */

public int size() {

return size;

}

/** Return an iterator for the elements in this set */

public java.util.Iterator iterator() {

return new MyHashSetIterator(this);

}

/** Inner class for iterator */

private class MyHashSetIterator implements java.util.Iterator {

// Store the elements in a list

private java.util.ArrayList list;

private int current = 0; // Point to the current element in list

MyHashSet set;

/** Create a list from the set */

public MyHashSetIterator(MyHashSet set) {

this.set = set;

list = setToList();

}

/** Next element for traversing? */

public boolean hasNext() {

if (current < list.size())

return true;

return false;

}

/** Get the current element and move cursor to the next */

public E next() {

return list.get(current++);

}

/** Remove the current element and refresh the list */

public void remove() {

// Delete the current element from the hash set

set.remove(list.get(current));

list.remove(current); // Remove the current element from the list

}

}

/** Hash function */

private int hash(int hashCode) {

return supplementalHash(hashCode) & (capacity - 1);

}

/** Ensure the hashing is evenly distributed */

private static int supplementalHash(int h) {

h ^= (h >>> 20) ^ (h >>> 12);

return h ^ (h >>> 7) ^ (h >>> 4);

}

/** Return a power of 2 for initialCapacity */

private int trimToPowerOf2(int initialCapacity) {

int capacity = 1;

while (capacity < initialCapacity) {

capacity <<= 1;

}

return capacity;

}

/** Remove all e from each bucket */

private void removeElements() {

for (int i = 0; i < capacity; i++) {

if (table[i] != null) {

table[i].clear();

}

}

}

/** Rehash the set */

private void rehash() {

java.util.ArrayList list = setToList(); // Copy to a list

capacity <<= 1; // Double capacity

table = new LinkedList[capacity]; // Create a new hash table

size = 0;

for (E element: list) {

add(element); // Add from the old table to the new table

}

}

/** Copy elements in the hash set to an array list */

private java.util.ArrayList setToList() {

java.util.ArrayList list = new java.util.ArrayList();

for (int i = 0; i < capacity; i++) {

if (table[i] != null) {

for (E e: table[i]) {

list.add(e);

}

}

}

return list;

}

/** Return a string representation for this set */

public String toString() {

java.util.ArrayList list = setToList();

StringBuilder builder = new StringBuilder("[");

// Add the elements except the last one to the string builder

for (int i = 0; i < list.size() - 1; i++) {

builder.append(list.get(i) + ", ");

}

// Add the last element in the list to the string builder

if (list.size() == 0)

builder.append("]");

else

builder.append(list.get(list.size() - 1) + "]");

return builder.toString();

}

}

我不太关注这一部分：

/** Ensure the hashing is evenly distributed */

private static int supplementalHash(int h) {

h ^= (h >>> 20) ^ (h >>> 12);

return h ^ (h >>> 7) ^ (h >>> 4);

}

操作都很清楚,但是它们如何确保均匀分布的散列？

关于此代码的另一个问题,在这部分：

/** Add an element to the set */

public boolean add(E e) {

if (contains(e))

return false;

if (size > capacity * loadFactorThreshold) {

if (capacity == MAXIMUM_CAPACITY)

throw new RuntimeException("Exceeding maximum capacity");

rehash();

}

int bucketIndex = hash(e.hashCode());

// Create a linked list for the bucket if it is not created

if (table[bucketIndex] == null) {

table[bucketIndex] = new LinkedList();

}

// Add e to hashTable[index]

table[bucketIndex].add(e);

size++; // Increase size

return true;

}

为什么不在尺寸后放置尺寸检查和重复块？

在电商促销或一些直播小游戏中，抽奖是一种比较常见的玩法。很多时候，展现给用户的可能是一个大转盘，如下：

通常我们会给出一堆奖品，每个奖品有各自的中奖概率，而且每个奖品可能还有库存的概念，就是说已经被抽完了的奖品是不再参与抽奖的。就拿陌陌里的这个大转盘来举例，奖品列表有爱心火箭、私人飞机、旋转木马、梦幻香水、口红、暖心奶茶、糖果、未中奖(未中奖可以看着是特殊的奖品)等8个奖品，每个奖品会根据其价值有不同的中奖概率，比如中糖果和暖心奶茶的概率高些，但中火箭的概率可能低很多。如果让你用java实现一个抽奖，你会怎么实现它呢？这正是我们今天要探讨的内容。

抽奖算法

在Java中，java.lang.Math.Random()方法本身基本可以保证大量测试的情况下避免高重复，且概率分布比较平均。所以我们根据奖品的概率列表基于java.lang.Math.Random()方法实现一个抽奖的工具类：

根据奖品的中奖概率列表probabilityList计算总概率sumRate；

根据总概率和各个奖品的概率对概率进行分块，得到分块列表blockList，比如传过来的概率列表是｛0.25,0.15,0.6｝,那么分块区间就是0-0.25，0.25-0.4,0.4-1.0，blockList的集合就是{0.25,0.4,1.0}；

根据java.lang.Math.Random()平均概率返回0到1之间数字的特性得到nextDouble;

把nextDouble的值按大小顺序插入到blockList中；

返回nextDouble插入的位置

抽奖逻辑

有了上面的抽奖算法，接下来我们分析下抽奖的逻辑是怎么实现的。为了更贴近使用场景，除了每个奖品有中奖概率外，增加一个库存的概念。因为有时候大奖并不是无限的，可能只有一个。在促销活动进行过程中，运营人员不一定一开始就把大奖的库存放出来，毕竟留在后面才更有悬念，如果大奖一放出来就被抽走了，用户的参与热情估计就没了，因为大家都是冲着大奖来的，就跟买彩票只想中500万一个道理。

定义一个奖品类Award，属性包含奖品名称、中奖概率、库存等。

接下来，我们模拟一下抽奖逻辑：

运行结果类似：

抽奖逻辑注意事项

上面的抽奖逻辑只是简单的单线程模拟抽奖算法的有效性，在生产环境中，还需要注意线程安全性、分布式事务等问题，抽奖都是高并发场景下，所以要处理好库存扣减以及库存扣减失败重抽等细节。

public class Fenpei {

static List listCus = new ArrayList();

static List persons = new ArrayList();

// static Map result = new HashMap();

static List result = new ArrayList();

/**

* @param args

*/

public static void main(String[] args) {

int k = 0;

List l = new ArrayList();

// 发、数量

for (int i = 0; i < 20; i++) {

listCus.add(i);

}

// 人

for (int j = 0; j < 5; j++) {

persons.add("person" + j);

}

// System.out.println(persons.size());

int personSize = persons.size();

for (int i = 0; i < listCus.size(); i++) {

// System.out.println(i);

// System.out.println(persons.get(i%personSize));

Persons p = new Persons();

p.setI(i);

p.setPersonname(persons.get(i % personSize));

result.add(p);

}

Iterator it = result.iterator();

while (it.hasNext()) {

Persons p = (Persons) it.next();

System.out.println("哪个人 => " + p.getI() + " 分配到 "

+ p.getPersonname());

}

// for (int j = 1; j < persons.size() + 1; j++) {

// System.out.println(j);

// }

}

public static class Persons {

private Integer i;

private String personname;

public Integer getI() {

return i;

}

public void setI(Integer i) {

this.i = i;

}

public String getPersonname() {

return personname;

}

public void setPersonname(String personname) {

this.personname = personname;

}

}

}

第二种方法

public class FenpeiRen {

/**

* @param args

*/

public static void main(String[] args) {

Person p1 = new Person("NAME1", 201);

Person p2 = new Person("NAME2", 233);

Person p3 = new Person("NAME3", 189);

Person p4 = new Person("NAME4", 198);

Person p5 = new Person("NAME5", 164);

Person p6 = new Person("NAME6", 181);

Person p7 = new Person("NAME7", 212);

Person p8 = new Person("NAME8", 205);

Person p9 = new Person("NAME9", 192);

Person p10 = new Person("NAME10", 241);

Person p11 = new Person("NAME11", 136);

Person p12 = new Person("NAME12", 201);

Person p13 = new Person("NAME13", 142);

Person p14 = new Person("NAME14", 127);

Person p15 = new Person("NAME15", 189);

Person p16 = new Person("NAME16", 221);

List personList = new ArrayList();

personList.add(p1);

personList.add(p2);

personList.add(p3);

personList.add(p4);

personList.add(p5);

personList.add(p6);

personList.add(p7);

personList.add(p8);

personList.add(p9);

personList.add(p10);

personList.add(p11);

personList.add(p12);

personList.add(p13);

personList.add(p14);

personList.add(p15);

personList.add(p16);

sort(personList,5);

}

/**

* 分组函数

*

* @param personList

* 总人数列表

* @param groupCount

* 分组数量

*/

static void sort(List personList, int groupCount) {

// 取得总人数

int personSize = personList.size();

// 如果分组数量小于personsize，则分组

if (groupCount <= personSize) {

// 先排序

Collections.sort(personList, new Comparator() {

public int compare(Person p1, Person p2) {

return p1.get_capability().compareTo(p2.get_capability());

}

});

// 可以取多少次

int qU = (personSize / groupCount) + 1;

List> pList = new ArrayList>();

// 排序后的数量

List> sortList = new ArrayList>();

// 分组排序后的数据

for (int i = 0; i < qU; i++) {

List getPerson = new ArrayList();

for (int j = 0; j < groupCount; j++) {

int index = 0;

if (j == 0) {

index = i + j;

} else {

index = (j) * groupCount + i;

}

if(index

getPerson.add(personList.get(index));

}

}

if(getPerson.size()>0){

sortList.add(getPerson);

}

}

//开始分配

for (int j = 0; j < groupCount; j++) {

List listPerson = new ArrayList();

boolean sort = true;

for (int i = 0; i < sortList.size(); i++) {

//正向分

if(sort){

if(j

listPerson.add(sortList.get(i).get(j));

}

sort=false;

}

else{//反向分

if(groupCount-(j+1)=0){

listPerson.add(sortList.get(i).get(groupCount-(j+1)));

}

sort=true;

}

}

if(listPerson.size()>0){

pList.add(listPerson);

}

}

int m = 0;

for (List lp : pList) {

m++;

System.out.print("当前第 "+m+" 组\r\n");

int totalCa = 0;

for(Person p : lp){

totalCa = totalCa + p.get_capability();

System.out.print("能力 "+p.get_capability()+" 名字 "+p.get_name());

}

System.out.print("总能力 "+totalCa+"\r\n");

System.out.print("结束\r\n");

}

}else{

System.out.println("无法分组，分组数量大于总人数\r\n");

}

// Collection.sort();

}

}

分享到：

2010-05-07 13:26

浏览 9489

评论

1 楼

qiankai86

2013-01-06

Thank you!