import java.util.*;

/**
 * 权重随机算法实现
 * a b c d 对应权重范围 --- [0,1)、[1,3)、[3,6)、[6,10)
 */
public class RandomSF {

    private static TreeMap<String, Integer> hm = new TreeMap<>();

    public static void main(String[] args) throws Exception {
        TreeMap<String, Integer> randomMap = new TreeMap<String, Integer>();
        randomMap.put("a", 1);
        randomMap.put("b", 2);
        randomMap.put("c", 3);
        randomMap.put("d", 4);
        Integer tmp = 0;
        ArrayList<ElementWeight> arr = new ArrayList<ElementWeight>();
        for (Map.Entry<String, Integer> entry : randomMap.entrySet()) {
            String key = entry.getKey();
            Integer value = entry.getValue();
            ElementWeight ew = new ElementWeight(key, tmp, tmp + value);
            tmp += value;
            arr.add(ew);
        }
        Random random = new Random();
        for (int j = 0; j < 100000000; j++) {
            int i = random.nextInt(tmp);
            String randomStr = binarySearch(arr, i);
            countRandomStr(randomStr);
        }
        for (ElementWeight ew:arr) {
            System.out.println(ew.getElement()+"的权重范围:"+"["+ew.getLow()+","+ew.getHigt()+")");
        }
        System.out.println(hm);
    }

//    二分查找实现
    public static String binarySearch(ArrayList<ElementWeight> arr, int num) {
        int high = arr.size();
        int low = 0;
        while (high >= low) {
            int middle = (high + low) / 2;
            ElementWeight ew = arr.get(middle);
            if (num >= ew.getLow() && num < ew.getHigt()) {
                return ew.getElement();
            } else if (num >= ew.getHigt()) {
                low = middle + 1;
            } else if (num < ew.getLow()) {
                high = middle - 1;
            }
        }
        return null;
    }

//  权重元素实体类
    static class ElementWeight {
        private String element;
        private Integer low;
        private Integer higt;

        public ElementWeight(String element, Integer low, Integer higt) {
            this.element = element;
            this.low = low;
            this.higt = higt;
        }

        public String getElement() {
            return element;
        }

        public Integer getLow() {
            return low;
        }

        public Integer getHigt() {
            return higt;
        }

    }

//  统计随机string的个数
    public static void countRandomStr(String str) {
        Integer value = hm.get(str);
        if (value == null) {
            hm.put(str, 1);
        } else {
            hm.put(str, ++value);
        }
    }
}